前缀和的后缀和

题目描述:

现在有一个数列$a_1,a_2,\dots ,a_n$，其前缀和$S_i=a_1+a_2+\cdots +a_i=\sum _{k=1}^i{a}_i$。

现在有2个操作，修改$a_i$的值，求$T_i=S_i+S_{i+1}+\cdots +S_n=\sum _{k=i}^n{S}_i$。

输入格式:

输入强制在线。

第1行3个数n（数列长度）,m（操作个数）,lastans初始值。

第2行n个数$a_1,a_2,\dots ,a_n$。

第3-m+2行每行3个数。

1 i j：修改$a_{(i+j+lastans)modn+1}$的值为j

2 i j：求$T_{(i+j+lastans)modn+1}$的值

输出格式:

对于每个2操作输出答案。

注意：输出答案后将lastans更新为上次的答案

样例输入:

5 3 2
1 2 3 4 5
2 3 2
1 4 2
2 3 3

样例输出:

31
28

提示:

$1\le n\le 100000$

$1\le m\le 300000$

$0\le$输入的$lastans\le {10}^{12}$

$0\le a_i\le 100000$

$0\le$操作输入的$i\le {10}^{12}$

$0\le$操作输入的$j\le 100000$

时间限制: 1000ms
空间限制: 256MB

---

来源: by qq1010903229