o339. 加盟店 - 高中生程式解題系統

內容

大黑廚師十分擅長經營餐廳，並且最終創立了一個加盟品牌，現在有$N$個員工以及$N$間加盟店，第$i$個員工分別在第$i$間加盟店工作$(1 \le i \le N)$，在一開始第$i$個加盟店的月薪是$S_i(1 \le i \le N)$。

在這瞬息萬變且競爭激烈的世界，披薩店並不好生存，在邪惡的駘北諡，每天會有$Q$個事件發生，有以下三種:

將第$b$個員工工作的店合併到第$a$個員工工作的店，共創強大，$b$和他所有的同事月薪會改為$a$工作的店的月薪，如果$a$跟$b$原本就在同一間店則忽略此操作。
第$a$個員工偷偷打廣告，使$a$工作的店家的月薪增加$R$
第$a$個員工拋棄原本工作的店並開設新店，並且新店的月薪為$C$

今天是發薪日，請你輸出所有員工會收到的薪水

輸入說明

第一行$T$為測資數量

第二行爲$N$, $Q$，分別是人數和事件數

第三行有$N$個數字，代表剛開始的月薪$S_i$

之後$Q$行會有三種輸入，輸入的開頭會有個數字$k$，對應題序的三種事件

$1\ a_i\ b_i$

$2\ a_i\ R_i$

$3\ a_i\ C_i$

$1 \le N, Q \le 10^6$

$k = 1, 2, 3$

$1 \le a_i, b_i \le N $

$0 \le S_i, R_i, C_i \le 10^9 $

輸出說明

每個測資輸出一行，照順序輸出第$i$位員工收到的薪水

範例輸入 #1

2
5 4
1 0 2 5 10
3 1 7
1 4 1
3 1 1
2 2 2
7 10
2 3 1 7 5 2 8
1 1 3
1 2 4
1 4 3
2 1 10
1 5 7
2 7 24
2 3 6
2 5 10
1 6 4
1 4 3

範例輸出 #1

1 2 2 5 10 
2 2 2 2 39 2 39

測資資訊：

記憶體限制： 256 MB
公開測資點#0 (26%): 2.0s , <1M
公開測資點#1 (34%): 2.0s , <1M
公開測資點#2 (4%): 2.0s , <10M
公開測資點#3 (4%): 2.0s , <50M
公開測資點#4 (4%): 2.0s , <50M
公開測資點#5 (4%): 2.0s , <50M
公開測資點#6 (4%): 2.0s , <10M
公開測資點#7 (4%): 2.0s , <50M
公開測資點#8 (4%): 2.0s , <50M
公開測資點#9 (4%): 2.0s , <50M
公開測資點#10 (4%): 2.0s , <50M
公開測資點#11 (4%): 2.0s , <50M

提示：

子題$1$
$1\le N, Q\le 1000$
26分

子題$2$
不會有第3筆操作
34分

子題$3$
原題
40分

標籤:

社內賽

出處:

[管理者： CGSH (快加油吧~~) ]

編號	身分	題目	主題	人氣	發表日期
沒有發現任何「解題報告」