98. 帝國的風雨飄搖

0 Judge

Code: 0


帝國的風雨飄搖

  • 在遙遠的非洲大陸上,有一個農業發達的帝國,帝國總共有$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