链接

https://www.lydsy.com/JudgeOnline/problem.php?id=1251

思路

好简单的模板题
不过还是wrong了好几发
叶子节点要注意下,不能使用
遇到就不管
写的fhq-treap，OI中常数最大的平衡树，中间还T了一发

代码

#include <iostream>
#include <ctime>
#include <cstdlib>
#include <cstdio>
using namespace std;
const int N=5e5+7;
int read() {
    int x=0,f=1;char s=getchar();
    for(;s>'9'||s<'0';s=getchar()) if(s=='-') f=-1;
    for(;s>='0'&&s<='9';s=getchar()) x=x*10+s-'0';
    return x*f;
}
int n,m;
int ch[N][2],val[N],pri[N],siz[N],ma[N],tag_1[N],tag_2[N];
int max(int a,int b) {
    return a>b?a:b;
}
void work1(int rt) {
    if(!rt) return;
    swap(ch[rt][0],ch[rt][1]);
    tag_1[rt]^=1;
}
void work2(int rt,int k) {
    if(!rt) return;
    val[rt]+=k;
    ma[rt]+=k;
    tag_2[rt]+=k;
}
void pushdown(int rt) {
    if(tag_1[rt]) {
        work1(ch[rt][0]);
        work1(ch[rt][1]);
        tag_1[rt]=0;
    }
    if(tag_2[rt]) {
        work2(ch[rt][0],tag_2[rt]);
        work2(ch[rt][1],tag_2[rt]);
        tag_2[rt]=0;
    }
}
void pushup(int rt) {
    ma[rt]=max(val[rt],max(ma[ch[rt][0]],ma[ch[rt][1]]));
    siz[rt]=siz[ch[rt][0]]+siz[ch[rt][1]]+1;
}
int cnt;
int build(int l,int r) {
    if(l>r) return 0;
    int mid=(l+r)>>1,p=++cnt;
    ma[p]=val[p]=0,pri[p]=rand(),siz[p]=1;
    ch[p][0]=build(l,mid-1);
    ch[p][1]=build(mid+1,r);
    if(!ch[p][0]) ma[ch[p][0]]=-0x3f3f3f3f;
    if(!ch[p][1]) ma[ch[p][1]]=-0x3f3f3f3f;
    pushup(p);
    return p;
}
int merge(int x,int y) {
    pushdown(x),pushdown(y);
    if(!x||!y) return x+y;
    if(pri[x]<pri[y]) {
        ch[x][1]=merge(ch[x][1],y);
        pushup(x);
        return x;
    } else {
        ch[y][0]=merge(x,ch[y][0]);
        pushup(y);
        return y;
    }
}
void split(int now,int &x,int &y,int k) {
    if(!now) x=y=0; 
    else {
        pushdown(now);
        if(siz[ch[now][0]]+1<=k)
            x=now,split(ch[now][1],ch[x][1],y,k-siz[ch[now][0]]-1);
        else 
            y=now,split(ch[now][0],x,ch[y][0],k);
        pushup(now);
    }
}
void debug(int now ){
    pushdown(now);
    if(!now) return;
    debug(ch[now][0]);
    cout<<val[now]<<" ";
    debug(ch[now][1]);
}
int main() {
    n=read(),m=read();
    int rt=build(1,n);
    for(int i=1;i<=m;++i) {
        int opt=read(),l=read(),r=read(),x,y,z;
        if(opt==1) {
            int v=read();
            split(rt,x,z,r);
            split(x,x,y,l-1);
            work2(y,v);
            rt=merge(merge(x,y),z);
        } 
        else if(opt==2) {
            split(rt,x,z,r);
            split(x,x,y,l-1);
            work1(y);
            rt=merge(merge(x,y),z);
        } else {
            split(rt,x,z,r);
            split(x,x,y,l-1);
            printf("%d\n",ma[y]);
            rt=merge(merge(x,y),z);
        }
        // debug(rt);puts("");
    }
    return 0;
}
/*
10 3
1 3 9 -5705
2 2 6 
3 7 8
*/