#include <cstdio>
#include <iostream>
using namespace std;
const int M = 100005;
const int inf = 0x3f3f3f3f;
int read()
{
	int x=0,f=1;char c;
	while((c=getchar())<'0' || c>'9') {if(c=='-') f=-1;}
	while(c>='0' && c<='9') {x=(x<<3)+(x<<1)+(c^48);c=getchar();}
	return x*f;
}
int n,m,p,a[M],mx[M<<2],tr[M<<2];
int ask(int i,int l,int r,int c)
{
	if(l==r) return mx[i]>c?c+l:inf;
	int mid=(l+r)>>1;
	return mx[i<<1|1]>c?min(tr[i],
	ask(i<<1|1,mid+1,r,c)):ask(i<<1,l,mid,c);
}
void ins(int i,int l,int r,int id,int c)
{
	if(l==r) {mx[i]=c-l;return ;}
	int mid=(l+r)>>1;
	if(mid>=id) ins(i<<1,l,mid,id,c);
	else ins(i<<1|1,mid+1,r,id,c);
	mx[i]=max(mx[i<<1],mx[i<<1|1]);
	tr[i]=ask(i<<1,l,mid,mx[i<<1|1]);
}
signed main()
{
	n=read();m=read();p=read();
	for(int i=1;i<=n;i++)
		ins(1,1,n,i,read());
	int ans=ask(1,1,n,mx[1]-n)+n;
	printf("%d\n",ans);
	while(m--)
	{
		int x=read()^(!p?0:ans),y=read()^(!p?0:ans);
		ins(1,1,n,x,y);ans=ask(1,1,n,mx[1]-n)+n;
		printf("%d\n",ans);
	}
}

C45 线段树+递归合并 P4425 [HNOI/AHOI2018] 转盘

/* 缝合题解  by hansang
转化问题：假设你 T时刻在某个点,每次可以向前走或者留在原地,然后 T减1
每个点在 t[i]时间消失,求一个最小的 T使得在所有点都消失前访问所有点
发现转化后可以将中途等待时间堆加到第一个点，答案不变，则有下：
 
1.破环为链，复制一遍到 n+1~2*n
2.枚举一个起点 i(1<=i<=n)，设 s时刻从 i出发，
  到达点 j的时间为 s+(j-i)
3. s+(j-i)必须大于 t[j]，则有：s=i+max{t[j]-j}(i<=j<=i+n-1)
4.总时间为：min{s+n-1}, j的范围(i<=j<=i+n-1)不太方便求答案，
  可以选择扩大右界至 2*n，答案不变，因为 t[i+n]=t[i],
  但 t[i+n]-(i+n)<t[i]-i，所以不影响答案
5.考虑使用线段树，总时间为：min{i+max{t[j]-j}}+n-1,
  每一个区间都维护 max{t[j]-j}和 min{i+max{t[j]-j}} (mx和 mi)
6.维护每一区间的左半段的 mx和 mi，右半段只维护 mx
  因为右区间的最大值配上左区间的 i会比配上右区间的 i更优，
7.考虑递归更新答案， 令右区间最大值为 x，把左区间分成lc 和 rc，
  (1)当左区间只有一个数时，用区间最小 i和 max(左区间最大值，x)更新答案
  (2)当左区间 rc最大值 mx小于等于 x时，左区间 rc最优答案为：tr[左区间 rc].l+x
     这时还要更新左区间 lc的贡献，递归即可
  (3)当左区间 rc最大值 mx大于 x时，可以使用左区间之前的答案(不受影响)，
     但左区间 rc还需递归，因为该区间最大值 mx右边的部分会用 x更新答案
8.线段树根节点tr[1].mi+n-1为最终答案，算答案前注意 p的取值
*/
#include<bits/stdc++.h>
using namespace std;
const int N=2e5+10;
int t[N];
#define lc(p) (p<<1)
#define rc(p) (p<<1)|1
struct node{int l, r, mx, mi;} tr[N*4];
int dfs(int p, int x)
{
    if(tr[p].l==tr[p].r) return tr[p].l+max(tr[p].mx, x); //(1)
    if(tr[rc(p)].mx<=x) return min(dfs(lc(p), x), tr[rc(p)].l+x); //(2)
    else return min(tr[p].mi, dfs(rc(p), x)); //(3)
}
void pushup(int p) 
{
    tr[p].mx=max(tr[lc(p)].mx, tr[rc(p)].mx); //更新 mx
    tr[p].mi=dfs(lc(p), tr[rc(p)].mx); 
    /*注意这里先不用 lc和 rc的 mi更新是因为
      lc是等确定(tr[rc(p)].mx>x)后再用，而rc的 mi没有更新过*/
}
void bt(int p, int l, int r)
{
    tr[p]={l, r, 0, 0}; int mid=(l+r)/2;
    if(l==r) {tr[p]={l, r, t[l]-l, t[l]}; return ;} //初始化，i+t[i]-i就等于t[i]
    bt(lc(p), l, mid); bt(rc(p), mid+1, r);
    pushup(p);
}
void change(int p, int x, int y)
{
    if(x<tr[p].l || x>tr[p].r) return ;
    if(tr[p].l==tr[p].r) {tr[p].mx=y-tr[p].l; tr[p].mi=y; return ;}
    change(lc(p), x, y); change(rc(p), x, y);
    pushup(p);
}
int main()
{
    int n, m, p; scanf("%d%d%d", &n, &m, &p);
    for(int i=1; i<=n; i++) scanf("%d", &t[i]), t[n+i]=t[i];
    bt(1, 1, 2*n); int last=tr[1].mi+n-1; printf("%d\n", last);
    while(m--)
    {
        int x, y; scanf("%d%d", &x, &y); 
        if(p==1) x^=last, y^=last;
        change(1, x, y); change(1, x+n, y);
        last=tr[1].mi+n-1; 
        printf("%d\n", last);
    }
    return 0;
}