泡泡與她的彈簧床(easy)

發布時間: Oct. 2, 2021, 2:54 p.m.   最後更新時間: Sept. 15, 2023, 8:37 p.m.   時間限制: 1000ms   記憶體限制: 128M

提醒: easy和hard兩題只差在$N, Q$的值域不同!


你與泡泡喝完下午茶後,她說她想要玩彈簧床!


她有個神奇的習慣: 她會先把$N$個彈簧床排成一列,選定一個起點$l$,然後$k$個$k$個跳下去直到超過第$r$個彈簧床,一超過她就會落在一旁的泡泡堆中(然後她就會很開心)。


每個彈簧床$i$都有一個數值$a_i$,即使她很期待跳到最後落入泡泡堆,她還是會專心地把所有碰到彈簧床上的數值加起來,畢竟她不想有任何無聊的時光,而數學正是個好方法。


然而,看著她玩了幾輪後,你發覺自己好無聊喔,於是你突發奇想,趁泡泡不注意時,改掉某些彈簧床上的數字。


在泡泡遊玩的時間內,泡泡玩彈簧床跟你改數字的次數正好有$Q$次,而在等待她跳完的時間,你發現你沒有其他事可以做了,所以你開始算起這次泡泡的答案。

第一行輸入有兩個正整數$N, Q$,以空白隔開
下一行有$N$個數字$a_i$,代表彈簧床上一開始的數值
接下來有$Q$行(輸入格式請參考範例測資)
如果是 $1, l, r, k$表示泡泡從$l$開始,$k$個$k$個跳下去直到超過$r$
如果是 $2, x, v$表示你把位置$x$的彈簧床上的數字改成$v$

$1\leq N, Q, k\leq2\times10^3$
$1\leq l, r\leq N$
$1\leq x\leq N$
$1\leq a_i\leq10^9$

對於每次泡泡玩彈簧床(即輸入$1, l, r, k$時)
輸出一行表示正確答案

複製範例
5 3
6 0 3 2 4
1 1 5 2
2 3 10
1 1 5 2
13
20

題目來源:NHDK Ten Point Round


其實我不知道這題在幹嘛 於是乎 其他的標籤交給各位電神了 (逃~

--Noter

模擬

竹中軟研35th第三次競賽(社內賽)