137. Day 2 PG. 我愛斯大林

我愛斯大林

題目敘述

• 「夏天夏天悄悄過去留下小祕密。斯大林斯大林❤真叫我回憶...」今天元首又在對著斯大林寄來的電報發情了，斯大林的電報為了防止他與元首間愛的火花被發現，採用了與一般電報不同的特殊編碼方式。

• 電報中，斯大林的訊息被加密放在一個序列$S$中，序列由$0$開始編號，要經過一些操作才能得到正確的資訊。斯大林給了元首$n,q,m,k$四個數字，其中$n$表示序列長度，接著會有$q$個操作，操作有兩種：

  • 0 a b：詢問區間$[a,b]$中有幾種不同的數字，保證$0 \leq a \leq b < n$
  • 1 x y：將$S[x]$修改成$(y \times preans\%m)\times k$，其中$preans$為上一次查詢的答案，保證$0 \leq x < n, 0 \leq y \leq 10^9$且在第一次修改之前一定會有至少一次查詢

• 對於每個詢問，回答出正確的答案就可以得到斯大林對元首愛的話語

  輸入說明

• 第一行有四個整數$n(1 \leq n \leq 10^5),q(1 \leq q \leq 2 \times 10^5),m(1 \leq m \leq 10^9),k(0 \leq k \leq 10^9)$，保證$m \times k \leq 10^9$。

• 接著有$n$個正整數，為序列$S[0] \sim S[n-1]$，保證數字都在int範圍。

• 接著有$q$行，每行有三個整數為題目要求的操作

輸出說明

• 對於每個查詢，輸出一個數字表示答案並換行

範例輸入

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

範例輸出

4
4
3

提示

new、malloc的速度是非常慢的，記憶體能用靜態就盡量用靜態。

Uva 12345

配分方法

• 10% $n \leq 100$
• 10% $n \leq 1000$
• 20% $n \leq 10^4$
• 60% $n \leq 10^5$

Judge Setting

run-time limit: 1500 ms
memory limit: 65536000 byte
測資數量: 0