Problem 4043 --交通中断4043: 交通中断
| Time Limit |
$1$ 秒/Second(s) |
Memory Limit |
$512$ 兆字节/Megabyte(s) |
| 提交总数 |
$5$ |
正确数量 |
$3$ |
"
| 裁判形式 |
标准裁判/Standard Judge |
我的状态 |
尚未尝试 |
| 难度 |
|
分类标签 |
|
当前分类(单击移除)：
单击选择分类：
Karen正在玩一款战略游戏。
在游戏中，Karen控制了n个星系，每个星系有一个能力值pi。它们在开始时是孤立的，但可以通过开
拓在两个星系间建立超空间航道。如果星系i可以直接或者间接地通过航道到达星系j，就称星系i和星
系j可以互相支援。星系i总是能够支援自己。
由于敌对方的破坏，有些航道可能会发生持久性的交通中断，并使得某些星系变得不再能互相支援。随
着游戏的进行，可能发生三类事件：
1. Karen下令开拓了一条航道（特别地，如果这条航道的两端在此时已经可以互相支援，工程队出于
节约考虑会忽略这条命令）；
2. 一条航道由于敌对方破坏而中断；
3. Karen想要知道，能够支援星系u的所有星系之中，第k小的能力值是多少。
你能处理好局面的变化，并正确回答Karen的询问吗？
输入的第1行包含2个整数n, m(1 ≤ n, m ≤ 2 × 105
)，表示星系总数。
接下来1行，包含n个整数，依次表示pi(1 ≤ pi ≤ 109
)。
接下来m行，按时间顺序描述所有事件。每行第一个整数opi表示事件的种类。
• 如果opi = 1，表示一条新航道建立。接下来2个整数ui
, vi(1 ≤ ui
, vi ≤ n)，表示建立了星系ui到星
系vi的超空间航道。注意如果ui
, vi此时可以互相支援，此事件不产生任何实际效果。
• 如果opi = 2，表示发生了一次交通中断。接下来2个整数ui
, vi(1 ≤ ui
, vi ≤ n)，表示星系ui到星
系vi的超空间航道遭到破坏。保证所描述的超空间航道在此时刻前存在且可用。
• 如果opi = 3，表示一次询问。接下来2个整数ui
, ki(1 ≤ ui ≤ n, 1 ≤ ki ≤ 20)，表示询问目前能支援
星系ui的所有星系之中，第k小的能力值。
对每次询问输出1行1个整数，表示那次询问的答案。特别地，如果能够支援星系ui的所有星系不足k个，
输出0。
约定
对于前20%的数据，n, m ≤ 5000。
另有50%的数据，在首次交通中断事件发生后不再有任何航道建立。
4 7
5 6 7 8
1 1 2
1 2 3
1 3 4
3 2 1
2 1 2
3 2 1
3 3 3
被破坏的航道可以在此后重新被开拓
| 本题记录 |
用 户（点击查看用户） |
运行号（点击购买题解） |
时 间 |
| 算法最快[$2 $ms]
|
realize
|
963146
|
2023-05-18 16:26:52 |
| 内存最少[$5176 $KB]
|
AOJ大管家
|
960490 |
2023-04-29 22:42:28 |
| 第一AC |
AOJ大管家 |
960490
|
2023-04-29 22:42:28 |
| 第一挑战 |
AOJ大管家
|
960490 |
2023-04-29 22:42:28 |
赛题来源/所属竞赛
N/A