近期博客可能停更。

Solution

https://www.cnblogs.com/NaVi-Awson/p/8918958.html

以下做一些补充。

一是当两个区间合并的时候，所谓可以直接用左区间 $lx$ 的左儿子的答案并不是指 $val_{lson(lx)}$，而是指 $val_{lx}$。

二是请不要忘记整个线段树是想要做什么。

三是为什么说这题和楼房重建很像，因为想想我们要求的东西：

i  1 2 3 4 5 6
ai 3 2 3 2 2 1

我们对它做一个后缀和看看？

i  1 2 3 4 5 6
Si 3 3 3 2 2 1

那么我们所需要考虑的只有连续的一段区间的最左边的答案（即按上面的例子只有 1,4,6 可能成为答案），因此启发我们维护一段连续向上的区间。

但是呢，个人认为事实上的实现跟这个确实没什么关系，只是方法上相似而已。即分类讨论，用 $\log$ 的时间 pushup。

Code

// Code by ajcxsu
// Problem: circle

#include<bits/stdc++.h>
using namespace std;

const int N=2e5+10;
#define ls(x) ((x)<<1)
#define rs(x) ((x)<<1|1)
int ma[N<<2], mi[N<<2], t[N];
int pup2(int a, int l, int r, int mx) { // merge a to z (mx=ma[z])
    if(l==r) return l+max(ma[a], mx);
    int mid=(l+r)>>1;
    if(ma[rs(a)]>=mx) return min(mi[a], pup2(rs(a), mid+1, r, mx));
    else return min(mid+1+mx, pup2(ls(a), l, mid, mx));
}
void pup(int x, int l, int mid) {
    ma[x]=max(ma[ls(x)], ma[rs(x)]),
    mi[x]=pup2(ls(x), l, mid, ma[rs(x)]);
}
void build(int x, int l, int r) {
    if(l==r) { ma[x]=t[l], mi[x]=l+t[l]; return; }
    int mid=(l+r)>>1;
    build(ls(x), l, mid), build(rs(x), mid+1, r);
    pup(x, l, mid);
}
void updata(int x, int l, int r, int d) {
    if(l==r) { ma[x]=t[l], mi[x]=l+t[l]; return; }
    int mid=(l+r)>>1;
    if(d<=mid) updata(ls(x), l, mid, d);
    else updata(rs(x), mid+1, r, d);
    pup(x, l, mid);
}

int main() {
    ios::sync_with_stdio(false), cin.tie(0);
    int n, m, p;
    cin>>n>>m>>p;
    for(int i=1;i<=n;i++) cin>>t[i], t[i+n]=t[i]-i-n, t[i]-=i;
    build(1, 1, n<<1);
    int lst;
    cout<<(lst=mi[1]+n-1)<<'\n';
    int x, y;
    while(m--) {
        if(!p) lst=0;
        cin>>x>>y, x^=lst, y^=lst; t[x]=y-x, t[x+n]=y-x-n;
        updata(1, 1, n<<1, x), updata(1, 1, n<<1, x+n);
        cout<<(lst=mi[1]+n-1)<<'\n';
    }
    return 0;
}