帝國的風雨飄搖
- 在遙遠的非洲大陸上,有一個農業發達的帝國,帝國總共有$n$座城市,有$m$條雙向道路將城市相連,資源非常不缺乏,肥料都一袋能頂兩袋撒。帝國會如此壯大的秘密來自於他們首席科學家最自豪的發明 -- 金坷垃,只要在肥料中摻了金坷垃,就不流失、不蒸發、零浪費。可惜好景不常,首席科學家的失蹤導致整個帝國大亂,各地因為沒有金坷垃的供應,叛亂四起、佔山為王、佔路為寇,民不聊生。
- 每個城市都有一間肥料公賣局,每個城市的肥料公賣局賣的肥料價格都不一樣,如果$A$城市可有一條路徑到達$B$城市,那$AB$城市的人可以互相到對方的城市買肥料。
- 因為內戰的關係,城市和城市間的道路常常因為戰火而被打斷。身為販賣肥料的商人,卦長經常會在各個城市中旅行,為了能更快速的在城市間移動,卦長曾經向首席科學家學習瞬間移動的能力,可以從一個城市瞬間移動到另一個城市,所以你的移動不會有影響。
- 卦長現在到了某個城市$p$,想知道現在這個城市的居民能到達的肥料公賣局中,比卦長肥料便宜的有多少間;以及詢問這個城市的居民能到達的肥料公賣局中,價格由小到大排序,排名第$k$的公賣局肥料價格是多少,請你寫個程式告訴卦長吧
輸入說明:
- 輸入的第一行會有兩個正整數$n,m$,表示城市數量及道路數量,城市、道路的編號由開1始
- 接著下一行有$n$個整數$C_1,C_2...C_n$,$C_i$表示第$i$個城市的肥料公賣局的肥料售價,$ 0 \leq C_i \leq 2^{31}-1$
- 再來有$m$行,第$i$行有兩個整數$a_i,b_i$,$ 1 \leq a_i,b_i \leq n$,表示城市$a_i,b_i$間有一條編號為$i$的雙向道路
- 接著有一個整數$t$($0<t \leq 1000000$),表示接下來有$t$個事件按造順序發生
- 事件有四種:
delete e
:戰火將編號為$e$的道路炸毀,$1 \leq e \leq m$,保證已經炸毀的路不會再被炸毀
rank p w
:卦長現在到了某個城市$p$,販賣的肥料價格為$w$,想知道現在這個城市的居民能到達的肥料公賣局中,比卦長肥料便宜的有多少間,$1 \leq p \leq n$,$ 0 \leq w \leq 2^{31}-1$
kth p k
:卦長現在到了某個城市$p$,想詢問這個城市的居民能到達的肥料公賣局中,價格由小到大排序,排名第$k$的公賣局肥料價格是多少,$1 \leq k \leq 居民能走到的城市數量$
change p w
:城市$p$的肥料公賣局將肥料的價格改成$w$
輸出說明
- 對於每個rank和kth的事件,輸出他們要求的值並換行
範例輸入:
3 3
10 20 30
1 2
2 3
1 3
13
delete 3
kth 1 2
rank 3 15
rank 2 10
rank 1 9
change 2 10
rank 1 10
rank 2 11
kth 2 1
delete 2
kth 3 1
change 1 50
kth 1 1
範例輸出:
20
1
0
0
0
2
10
30
10
配分:
配分 |
限制 |
20% |
$1 \leq n \leq 10,1 \leq m \leq 1000000$ |
20% |
$1 \leq n \leq 1000,1 \leq m \leq 1000000$ |
60% |
$1 \leq n \leq 100000,1 \leq m \leq 1000000$ |
時限 |
2000ms |
記憶體 |
51200000 kb |
Judge Setting
run-time limit: 2000 ms
memory limit: 51200000 byte
測資數量: 0