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

內容

大黑廚師十分擅長經營餐廳，並且最終創立了一個加盟品牌，現在有 $N$ 個員工以及 $N$ 間加盟店，第 $i$ 個員工分別在第 $i$ 間加盟店工作 $(1 \leq i \leq N)$ ，在一開始第 $i$ 個加盟店的月薪是 $S_{i} (1 \leq i \leq 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 \leq N, Q \leq 10^{6}$

$k = 1, 2, 3$

$1 \leq a_{i}, b_{i} \leq N$

$0 \leq S_{i}, R_{i}, C_{i} \leq 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 \leq N, Q \leq 1000$
26分

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

子題 $3$
原題
40分

標籤:

社內賽

出處:

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

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