题意：
有 (n) 个格子围成一圈，每个格子里有一个物品，每个物品的出现时间为 (T_i) 。开始时选择一个格子为起点，每个单位时间可以向前走一格或不动，若当前格的物品已出现则将其标记。有 (m) 次修改，每次修改一个物品的出现时间，并询问将所有物品标记的最短时间。
题解：
猜一下一个最优方案：选择一个点后停留一段时间后直接走一圈标记所有物品。感性分析一下是对的，因为多走超过一圈的地方可以用等待来代替。具体分析或证明可以看其他神仙的博客。
那么得到柿子：
[ans=displaystyle min _{i=1}^n { max_{j=i}^{i+n-1} {T_j-(j-i)}}+n-1
]
（前者为最大等待时间）。
整理一下柿子，设 (a_j=T_j-j) ：
[ans=displaystyle min _{i=1}^n { max_{j=i}^{i+n-1} {a_j}+i}+n-1
]
我们发现对于 ([i+ n,2n]) 的答案显然不会更优，所以我们减少一下限制，即：
[ans=displaystyle min _{i=1}^n { max_{j=i}^{2n} {a_j}+i}+n-1
]
发现最后对答案可能产生贡献的点的 (a_j) 一定从右到左单增。
于是我们直接用线段树维护区间最大值和 (min_{i=l}^{r/2}{max_{j=l}^{r}{a_j}+i})即可，即维护一个单调栈。时间复杂度为 (O(mlog^2 n)) .
#include<cstdio>
#include<algorithm>
using namespace std;
inline int gi()
{
char c; int x=0;
for(;c<'0'||c>'9';c=getchar());
for(;c>='0'&&c<='9';c=getchar())x=(x<<1)+(x<<3)+c-'0';
return x;
}
const int N=200005;
int n,m,p,ans,t[N],st[N<<2],mx[N<<2];
#define lx (x<<1)
#define rx (x<<1|1)
int query(int x, int l, int r, int w)
{
if(l==r) return l+max(w,mx[x]);
int mid=l+r>>1;
if(mx[rx]>=w) return min(st[x],query(rx,mid+1,r,w));
return min(mid+1+w,query(lx,l,mid,w));
}
void pushup(int x, int l, int r)
{
int mid=l+r>>1;
mx[x]=max(mx[lx],mx[rx]);
st[x]=query(lx,l,mid,mx[rx]);
}
void build(int x, int l, int r)
{
if(l==r)
{
mx[x]=t[l],st[x]=t[l]+l;
return ;
}
int mid=l+r>>1;
build(lx,l,mid),build(rx,mid+1,r);
pushup(x,l,r);
}
void update(int x, int l, int r, int s)
{
if(l==r)
{
mx[x]=t[l],st[x]=t[l]+l;
return ;
}
int mid=l+r>>1;
s<=mid?update(lx,l,mid,s):update(rx,mid+1,r,s);
pushup(x,l,r);
}
int main()
{
#ifndef ONLINE_JUDGE
freopen("circle.in","r",stdin);
freopen("circle.out","w",stdout);
#endif
n=gi(),m=gi(),p=gi();
for(int i=1;i<=n;++i) t[i]=gi()-i,t[i+n]=t[i]-n;
build(1,1,n<<1);
printf("%d
",ans=st[1]+n-1);
while(m--)
{
ans*=p;
int x=gi()^ans,y=gi()^ans;
t[x]=y-x,t[x+n]=t[x]-n;
update(1,1,n<<1,x),update(1,1,n<<1,x+n);
printf("%d
",ans=st[1]+n-1);
}
}