TopCoder

$(pr)^3pony$
https://prprprpony.github.io/blog/ $\\\huge PinkiePie:"OkieDokieLokie"$

User's AC Ratio

100.0% (4/4)

Submission's AC Ratio

64.7% (11/17)

Tags

Description

「想成為序列操作之神嗎? 在序列的世界輸贏一番吧! 」

電仁的意識漸漸清楚,思考著剛剛所聽到的話的同時,逐漸張開眼睛注視著四周,發現了自己身處於一個未知的世界之中,並且旁邊躺著一位蘿莉殿壬。

突然間,蘿莉殿壬說話了:「來自異世界的勇者呀! 請你拯救這個世界,戰勝這個世界的神 — 王彥仁吧! 」

「這種小說才會發生的事情,居然發生在自己的身上了!我果然有主角光環! 」電仁心想。

這是一個充滿著序列的世界,序列征戰的排行將決定在這個世界的地位,弱肉強食的情況也隨處可見。想要提升排行,必須透過序列征戰系統與他人對決。而序列征戰排行第一的人,也就是這個世界的神,可以改變世界一切法則。

充滿著正義感的電仁想要改變這個世界,於是他決定挑戰序列操作之神 — 王彥仁。

見到王彥仁後,電仁發現了,原來召喚電仁到這個世界的人,不是他人,不是蘿莉殿壬,正是這個世界的神 — 王彥仁。王彥仁長年以來一直在等待擁有強大序列實力的人來挑戰他,然而等了880301年,還是等待不到,因此他決定用召喚的方式,找異世界的強者輸贏,而召喚出來的這位強者就是電仁。

「你想成為序列操作之神嗎? 來輸贏吧! 來自異世界的強者! 」

在序列征戰中,系統將會隨機產生一道跟序列相關的題目,先解出該題的人即為贏家。這場異世界的頂尖對決終於要開始了,究竟序列征戰系統會出現怎麼樣的題目呢?

給定四個整數$N, Q, C, P$以及一個長度為N的序列$A_1, A_2, \ldots, A_N$,序列中每個數值皆介於$[0, 10^ 6]$,接下來有$Q$次操作,每次操作形式為以下三種中的一種:

  • 1 l r: 代表要把序列中第$L$項至第$R$項的每個數字$A_i$變成$C^ {A_i}$ ($L \le i \le R$)
  • 2 l r: 代表要詢問$(A_L + A_{L + 1} + \cdots + A_R) \bmod P$的結果
  • 3 p v: 代表要把序列的第$p$項數字變成$v$,即$A_p = v$

電仁看到這道題目後整個驚呆了,完全不知從何著手,可以請你幫幫電仁,讓他可以戰勝這場序列征戰,改變這個世界嗎?

Input Format

以下所有符號意義皆與序列征戰系統題目中的意義相同。

測試資料第一行包含四個正整數 $N, Q, C, P$。

接下來的一行,有$N$個整數,依序為序列中的每一項數值$A_1, A_2, \ldots, A_N$。

接下來 $Q$ 行,每行表示一個操作「1 l r」、「2 l r」或「3 p v」。

  • $1 \le N \le 10^ 5$
  • $1 \le Q \le 5 \times 10^ 4$
  • $1 \le C \le 10^ 6$
  • $1 \le P \le 10^ 3$
  • $0 \le A_i \le 10^ 6$
  • $1 \le l \le r \le N$
  • $1 \le p \le N$
  • $0 \le v \le 10^ 6$

Output Format

對於每個第 2 種操作,輸出一行,表示該次詢問的結果。

Sample Input 1

5 7 2 3
0 1 2 3 4
2 1 5
1 1 5
2 1 5
1 1 5
2 1 5
3 1 5
2 1 5

Sample Output 1

1
1
0
0

Sample Input 2

3 4 10 13
9 17 33
1 2 3
2 1 3
3 1 8
2 1 3

Sample Output 2

12
11

Hints

Problem Source

Subtasks

No. Testdata Range Score

Testdata and Limits

No. Time Limit (ms) Memory Limit (VSS, KiB) Output Limit (KiB) Subtasks
0 3000 262144 262144
1 3000 262144 262144
2 3000 262144 262144
3 3000 262144 262144
4 3000 262144 262144
5 3000 262144 262144
6 3000 262144 262144
7 3000 262144 262144
8 3000 262144 262144
9 3000 262144 262144
10 3000 262144 262144
11 3000 262144 262144
12 3000 262144 262144
13 3000 262144 262144
14 3000 262144 262144
15 3000 262144 262144
16 3000 262144 262144
17 3000 262144 262144
18 3000 262144 262144
19 3000 262144 262144
20 3000 262144 262144
21 3000 262144 262144
22 3000 262144 262144
23 3000 262144 262144
24 3000 262144 262144
25 3000 262144 262144
26 3000 262144 262144
27 3000 262144 262144
28 3000 262144 262144
29 3000 262144 262144
30 3000 262144 262144
31 3000 262144 262144
32 3000 262144 262144
33 3000 262144 262144
34 3000 262144 262144