泡泡與她的彈簧床(hard)
發布時間: Oct. 2, 2021, 2:54 p.m. 最後更新時間: Sept. 15, 2023, 9 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^5$
$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
