TopCoder

User's AC Ratio

92.9% (13/14)

Submission's AC Ratio

47.5% (56/118)

Tags

Description

殿壬是個天才兒童,他在一個月大的時候就學會數數、六個月大的時候就學會乘法跟除法、一歲時學會寫程式、一歲又六個月時養了可愛的拉不拉多、一歲又十個月時養了可愛的貓咪、兩歲時發明了「吃餅乾」的遊戲,而現在要講的,是殿壬三歲大時的故事。

殿壬三歲時,克服了天生對 蝴蝶 的恐懼,開始接受蝴蝶這個會 的生物。同時,他也對於觀察蝴蝶的有著異常的興趣。

現在,殿壬來到了一座森林,森林中總共有 $N$ 隻蝴蝶(蝴蝶以 $1$ 到 $N$ 編號),第 $i$ 隻蝴蝶的美度為 $a_i$,同時森林中也有 $N$ 棵樹(樹以 $1$ 到 $N$ 編號)。一棵樹只能棲息一隻蝴蝶。一開始的時候,第 $i$ 隻蝴蝶會棲息在第 $i$ 棵樹上。

現在,根據殿壬的觀察,蝴蝶會發生以下的事件:

  • $1 \ i \ j$ :編號為 $i$ 的蝴蝶 跟編號為 $j$ 的 蝴蝶 交換彼此棲息的樹。也就是說,編號為 $i$ 的蝴蝶會飛到標號為 $j$ 的蝴蝶原本所棲息的樹,編號為 $j$ 的蝴蝶會飛到編號為 $i$ 的蝴蝶所棲息的樹。
  • $2 \ i \ j$ :位於編號為 $i$ 的 的蝴蝶跟位於編號為 $j$ 的 的蝴蝶交換彼此棲息的樹。
  • $3 \ i \ w$ :把編號為 $i$ 的 蝴蝶 的美度改成 $w$ 。
  • $4 \ i \ w$ :把位於編號為 $i$ 的 上的蝴蝶的美度改成 $w$ 。
  • $5 \ L_1 \ R_1 \ L_2 \ R_2$ :位於編號為 $L_1$ 的樹的蝴蝶跟位於編號為 $L_2$ 的樹的蝴蝶交換彼此棲息的樹、位於編號為 $L_1 + 1$ 的樹的蝴蝶跟位於編號為 $L_2 + 1$ 的樹的蝴蝶交換彼此棲息的樹$......$、位於編號為 $R_1$ 的樹的蝴蝶跟位於編號為 $R_2$ 的樹的蝴蝶交換彼此棲息的樹。

而在發生事件的同時,殿壬也會想要知道一些資訊:

  • $6 \ i$ :殿壬想要知道位於編號為 $i$ 的 上蝴蝶的編號。
  • $7 \ i$ :殿壬想要知道編號為 $i$ 的 蝴蝶 所棲息的樹的編號。
  • $8 \ L \ R$:殿壬想要知道,編號為 $L$ 的 蝴蝶 到編號為 $R$ 的 蝴蝶 的美度總和。
  • $9 \ L \ R$:殿壬想要知道,棲息在編號為 $L$ 的 上的蝴蝶的美度到棲息在編號為 $R$ 的 上的蝴蝶的美度總和。

現在,身為殿壬的小幫手,你決定幫幫殿壬,當他需要知道一些資訊時,請你告訴他正確的答案。

Input Format

輸入的第一行包含兩個正整數 $N, Q$ ,$N$ 的作用已經在題目敘述說明,$Q$ 是殿壬觀察到事件的個數加上殿壬想要知道的資訊個數。

接下來的一行包含 $N$ 個整數,第 $i$ 個整數為 $a_i$,意義已經在題目敘述說明過。

接下來的 $Q$ 行,每行 依序 不外忽是殿壬觀察的事件,或是殿壬想要知道一些資訊。這 $Q$ 行的格式如題目敘述所述。

  • $1 \le N, Q \le 2 \times 10^ 5$
  • $1 \le a_i, w \le 1000$
  • $1 \le i, j \le N$
  • $1 \le L_1 \le R_1 < L_2 \le R_2 \le N$ ,並且$R_1 - L_1 = R_2 - L_2$
  • $1 \le L \le R \le N$

Output Format

對於每個殿壬想要知道的資訊,輸出相對應的數字。

Sample Input 1

7 10
13 44 32 11 72 24 84
8 1 3
1 3 6
7 6
2 1 4
6 1
5 1 3 5 7
9 1 3
3 4 46
4 3 10
9 3 4

Sample Output 1

89
3
4
188
23

Hints

這是另一個平行世界的殿壬。很遺憾的,在我們所身處的平行世界,你還是只能看到很怕蝴蝶的殿壬。

Problem Source

Subtasks

No. Testdata Range Score
1 0~5 1

Testdata and Limits

No. Time Limit (ms) Memory Limit (VSS, KiB) Output Limit (KiB) Subtasks
0 2000 524288 262144 1
1 2000 524288 262144 1
2 2000 524288 262144 1
3 2000 524288 262144 1
4 2000 524288 262144 1
5 2000 524288 262144 1