通过这题，我发现了我最大的缺陷，就是题目中重要的性质发现不了，所以导致后期根本做不了。还是要多做题，培养思维
对于这道题，来发现性质吧
对于每一条路线，因为它有用的就是最终的时刻，所以我们都可以把它变成一条由中间一个点出发，在起点等待一些时刻，然后接下来的每个时刻都向右走，在同一时刻完成任务
可以知道，每个路线都是可以这样转化的
所以我们要考虑的路线就只有在起点等待，然后不断向右走的路线
然后就有了这么一个式子（数组加长一倍，去掉环的影响）
(ans=min_{1 leq i leq n}{max_{0 leq j leq n-1} {T_{i+j}-j}+n-1})
因为每种路线的瓶颈在于过每个点作 (y=x+b) 的线后（先要把点的时刻转化成二位平面内的点），最上方的那根线，所以取max找那根线，然后再取min，找所有路线的最优解
继续推，(ans=min_{1leq i leq n}{max_{i leq j leq i+n-1}{T_j-j+i}+n-1}=min_{1leq i leq n}{max_{i leq j leq i+n-1}{T_j-j}+i+n-1})
因为max的范围让我们很不爽，不好一起维护，于是考虑把max的范围改一下，而又不影响答案
发现因为 (T_j=T_{j+n}) ， 所以 (T_j-j>T_{j+n}-j-n)，那么我们就算多考虑到复制的数组里去，由于我们找的是max，所以也不会影响答案
于是max的范围就变成了 (2n) ， (ans=min_{1leq i leq n}{max_{i leq j leq 2n}{T_j-j}+i}+n-1)
然后就要对于每个 (i) ，既要维护这个东西， (max_{i leq j leq 2n}{T_j-j}+i)，又要维护所有 (i) 的这个东西的min
那就用线段树
线段树对于每个区间维护两个东西，一个是整块区间的max，另一个是左半区间的答案（就是上面那个式子）
类似于楼房重建去修改和查询就可以了
#include<bits/stdc++.h>
#define ui unsigned int
#define ll long long
#define db double
#define ld long double
#define ull unsigned long long
const int MAXN=100000+10,inf=0x3f3f3f3f;
int n,m,p,ans;
template<typename T> inline void read(T &x)
{
T data=0,w=1;
char ch=0;
while(ch!='-'&&(ch<'0'||ch>'9'))ch=getchar();
if(ch=='-')w=-1,ch=getchar();
while(ch>='0'&&ch<='9')data=((T)data<<3)+((T)data<<1)+(ch^'0'),ch=getchar();
x=data*w;
}
template<typename T> inline void write(T x,char ch=' ')
{
if(x<0)putchar('-'),x=-x;
if(x>9)write(x/10);
putchar(x%10+'0');
if(ch!=' ')putchar(ch);
}
template<typename T> inline void chkmin(T &x,T y){x=(y<x?y:x);}
template<typename T> inline void chkmax(T &x,T y){x=(y>x?y:x);}
template<typename T> inline T min(T x,T y){return x<y?x:y;}
template<typename T> inline T max(T x,T y){return x>y?x:y;}
#define Mid ((l+r)>>1)
#define ls rt<<1
#define rs rt<<1|1
#define lson ls,l,Mid
#define rson rs,Mid+1,r
struct Segment_Tree{
int Mx[MAXN<<3],Mn[MAXN<<3];
inline int Query(int rt,int l,int r,int lmtR,int arMx)
{
if(l==r)return min(l!=lmtR?l+1+arMx:inf,max(arMx,Mx[rt])+l);
else
{
if(arMx>=Mx[rs])return Query(lson,lmtR,arMx);
else return min(Mn[rt],Query(rson,lmtR,arMx));
}
}
inline void PushUp(int rt,int l,int r)
{
Mx[rt]=max(Mx[ls],Mx[rs]);
if(l<=n)Mn[rt]=Query(lson,Mid,Mx[rs]);
}
inline void Update(int rt,int l,int r,int pos,int k)
{
if(l==r)Mx[rt]=k;
else
{
if(pos<=Mid)Update(lson,pos,k);
else Update(rson,pos,k);
PushUp(rt,l,r);
}
}
};
Segment_Tree T;
#undef Mid
#undef ls
#undef rs
#undef lson
#undef rson
int main()
{
freopen("circle.in","r",stdin);
freopen("circle.out","w",stdout);
read(n);read(m);read(p);
for(register int i=1;i<=n;++i)
{
int x;read(x);
T.Update(1,1,n<<1,i,x-i);T.Update(1,1,n<<1,i+n,x-i-n);
}
write(ans=T.Mn[1]+n-1,'
');
while(m--)
{
int x,y;read(x);read(y);
if(p)x^=ans,y^=ans;
T.Update(1,1,n<<1,x,y-x);T.Update(1,1,n<<1,x+n,y-x-n);
write(ans=T.Mn[1]+n-1,'
');
}
return 0;
}