题目
题解
假设起点固定，那么走的长度肯定是一圈$+x$
这样如果先停留时间$x$，再从$x+1$走的话就可以直接走一圈完事了
所以这样只用求开始在起点停留多少时间然后$+n-1$即可
设$t_i=T_i-i$，表示走到这里物品刚好出现需要停留的时间
则有答案为$\min_{i=1}^n(\max(t_{i…2n})+i)$
这样可以线段树维护了，根据右区间最大值来递归更新左区间答案，复杂度$O(n\log n^2)$
代码
# include<iostream>
# include<cstring>
# include<cstdio>
# include<algorithm>
# define tl (k<<1)
# define tr (k<<1|1)
# define mid (l+r>>1)
using namespace std;
const int MAX=2e5+5;
struct p{
int x,t;
}s[MAX<<2];
int n,m,p,ans;
int T[MAX];
int read()
{
int x(0);
char ch=getchar();
for(;!isdigit(ch);ch=getchar());
for(;isdigit(ch);x=x*10+ch-48,ch=getchar());
return x;
}
int ask(int l,int r,int k,int Mx)
{
if(l==r) return max(s[k].x,Mx)+l;
if(s[tr].x>=Mx) return min(s[k].t,ask(mid+1,r,tr,Mx));
return min(ask(l,mid,tl,Mx),Mx+mid+1);
}
void pus(int l,int r,int k) {s[k].t=ask(l,mid,tl,s[tr].x),s[k].x=max(s[tl].x,s[tr].x);}
void build(int l=1,int r=2*n,int k=1)
{
if(l==r) return void(s[k].t=(s[k].x=T[l]-l)+l);
build(l,mid,tl),build(mid+1,r,tr),pus(l,r,k);
}
void change(int l,int r,int k,int x,int d)
{
if(l==r) return void(s[k].t=(s[k].x=d-l)+l);
if(x<=mid) change(l,mid,tl,x,d);
else change(mid+1,r,tr,x,d);
pus(l,r,k);
}
int main()
{
n=read(),m=read(),p=read();
for(int i=1;i<=n;++i)
T[i+n]=T[i]=read();
build(),printf("%d\n",ans=s[1].t+n-1);
for(int i=1,x,y;i<=m;++i)
{
x=read(),y=read();
if(p) x^=ans,y^=ans;
change(1,2*n,1,x,y),change(1,2*n,1,x+n,y),printf("%d\n",ans=s[1].t+n-1);
}
return 0;
}
