题意：
分析：
-
暴力
只会 (40pts) 的暴力还让我写成了 (30pts) ，首先我们会在链上处理这个问题，(f_i=max(t_i,f_{i-1}+1))
转化一下式子
(f_i-i=max(t_i-i,f_{i-1}-(i-1)))
我们记 (A_i=f_i-i)
( herefore A_i=max(t_i-i,A_{i-1}))
( f_i=A_i+i=max(t_j-j)+i)
所以采取倍增然后断环为链的方式，维护一下每一个长度为 (n) 的区间里面 (t_j-j) 的最大值，用单调队列可以做到总复杂度 (O(mn)) 的然后我一看见单点修改，区间查询 想都没想直接上线段树，凭空多出来一个 (log)
-
正解：
我们接着上面的式子
(ans=displaystyle min_{i=1}^n {max_{j=0}^{n-1}{t_{i+j}-j}+n-1})
更改一下 (j) 的枚举得到
(ans=displaystyle min_{i=1}^n {max_{j=i}^{n+i-1}{t_j-(j-i)}+n-1})
(ans=displaystyle min_{i=1}^n {max_{j=i}^{n+i-1}{t_j-j}+n+i-1})
然后关键的一步来了
(ecause t_i-i>t_{i+n}-(i+n)) ( herefore [i,n+i-1]) 的最大值 等价于 ([i,2n]) 的最大值，也就是说我们不需要维护区间最值了，直接维护全局的后缀最值就可以了
虽然这种转换目前来看似乎不能直接优化复杂度
但是,我们接着考虑，每一个固定的 (t_j-j) 对应一段固定后缀，那么对于 (j) ,它取得最优值（即 (max(t_j-j+i) ) 的地方是 (i) 满足 (t_{i-1}-(i-1)>t_j-j) 也就是在它前面第一个比它大的元素的后一位 ，这也就告诉我们只需要维护一个类似单调栈的结构，就能直接求出每一段最优值，但是我们需要这个单调栈支持动态修改，做过 楼房重建 的巨佬就会发现，这道题就是线段树维护单调栈
放到这个题上具体来说就是：
建一颗线段树，每一个节点维护一个 (mx,val) 其中 (mx) 表示区间 (t_i-i) 的最大值， (val) 表示区间 ((t_j-j)+i) 的最小值 ( 这个 (val) 就相当于单调栈中一个元素，和它前面第一个比他大的元素的下一位的下标之和）
每一次 (pushup) 的时候，对于 (mx) 直接区间取 (max) ,而对于 (val) 要进行二分查找，这个区间的 (val) 就是用右区间的 (mx) 在左区间中找到一个位置 (i) 满足 (i) 是 (t_i-i) 小于 (mx) 的下标最小的值，查找的时候顺便和子区间的 (val) 取一下 (min)
总复杂度 (O(mlog ^2)) 线段树上二分两只 ( log)
代码：
#include<bits/stdc++.h>
#define pii pair<int,int>
#define mk(x,y) make_pair(x,y)
#define lc rt<<1
#define rc rt<<1|1
#define pb push_back
#define fir first
#define sec second
#define inl inline
#define reg register
using namespace std;
namespace zzc
{
inline int read()
{
int x=0,f=1;char ch=getchar();
while (!isdigit(ch)){if (ch=='-') f=-1;ch=getchar();}
while (isdigit(ch)){x=x*10+ch-48;ch=getchar();}
return x*f;
}
const int maxn = 3e5+5;
int n,m,lst,p;
int mx[maxn<<2],val[maxn<<2],t[maxn<<1];
int query(int rt,int l,int r,int x)
{
if(l==r) return l+max(x,mx[rt]);
int mid=(l+r)>>1;
if(mx[rc]<=x) return min(mid+1+x,query(lc,l,mid,x));
else return min(val[rt],query(rc,mid+1,r,x));
}
void pushup(int rt,int l,int r)
{
int mid=(l+r)>>1;
mx[rt]=max(mx[lc],mx[rc]);
val[rt]=query(lc,l,mid,mx[rc]);
}
void modify(int rt,int l,int r,int pos,int x)
{
if(l==r)
{
mx[rt]=x-l;
val[rt]=x;
return ;
}
int mid=(l+r)>>1;
if(pos<=mid) modify(lc,l,mid,pos,x);
else modify(rc,mid+1,r,pos,x);
pushup(rt,l,r);
}
void build(int rt,int l,int r)
{
if(l==r)
{
mx[rt]=t[l]-l;
val[rt]=t[l];
return ;
}
int mid=(l+r)>>1;
build(lc,l,mid);build(rc,mid+1,r);
pushup(rt,l,r);
}
void work()
{
int x,y;
n=read();m=read();p=read();
for(int i=1;i<=n;i++) t[i]=t[i+n]=read();
build(1,1,2*n);
printf("%d
",lst=val[1]+n-1);
while(m--)
{
x=read()^(lst*p);y=read()^(lst*p);
modify(1,1,2*n,x,y);
modify(1,1,2*n,x+n,y);
printf("%d
",lst=val[1]+n-1);
}
}
}
int main()
{
zzc::work();
return 0;
}