直角三角形

#include<cstdio>

#include<cstdlib>

#include<iostream>

#define ls(p) fhq[(p)].l

#define rs(p) fhq[(p)].r

using namespace std;

const int N=5e4+10;

struct fhqTreap{

    int l,r;

    int key,size,val;

    bool rev;int tag,maxn;

}fhq[N];

int cnt,rt,n,m;

inline int newnode(int val){

    fhq[++cnt].maxn=fhq[cnt].val=val;

    fhq[cnt].key=rand();

    fhq[cnt].size=1;

    return cnt;

}

inline void pushup(int now){

    fhq[now].size=fhq[ls(now)].size+fhq[rs(now)].size+1;

    fhq[now].maxn=fhq[now].val;

    if(ls(now))fhq[now].maxn=max(fhq[ls(now)].maxn,fhq[now].maxn);

    if(rs(now))fhq[now].maxn=max(fhq[rs(now)].maxn,fhq[now].maxn);

}

inline void pushdown(int now){

    if(fhq[now].rev){

        swap(ls(now),rs(now));

        fhq[ls(now)].rev^=1;fhq[rs(now)].rev^=1;

        fhq[now].rev=false;

    }

    if(fhq[now].tag){

        if(ls(now)){

            fhq[ls(now)].val+=fhq[now].tag; 

            fhq[ls(now)].tag+=fhq[now].tag;

        }if(rs(now)){ 

            fhq[rs(now)].val+=fhq[now].tag;

            fhq[rs(now)].tag+=fhq[now].tag;

        }

        fhq[now].tag=0;

    }

}

void split(int now,int sz,int &x,int &y){

    if(!now)x=y=0;

    else {

        pushdown(now);

        if(fhq[ls(now)].size<sz){

            x=now;split(rs(now),sz-fhq[ls(now)].size-1,rs(now),y);

        }else {

            y=now;split(ls(now),sz,x,ls(now));

        }

        pushup(now);

    }

}

int merge(int x,int y){

    if(!x||!y)return x|y;

    if(fhq[x].key>fhq[y].key){

        pushdown(x);

        rs(x)=merge(rs(x),y);

        pushup(x);return x;

    }else {

        pushdown(y);

        ls(y)=merge(x,ls(y));

        pushup(y);return y;

    }

}

inline void add(int l,int r,int val){

    int x,y,z;

    split(rt,l-1,x,y);

    split(y,r-l+1,y,z);

    fhq[y].tag+=val;

    fhq[y].val+=val;

    fhq[y].maxn+=val;

    rt=merge(merge(x,y),z);

}

inline void reverse(int l,int r){

    int x,y,z;

    split(rt,l-1,x,y);

    split(y,r-l+1,y,z);

    fhq[y].rev^=1;

    rt=merge(merge(x,y),z);

}

inline void query(int l,int r){

    int x,y,z;

    split(rt,l-1,x,y);

    split(y,r-l+1,y,z);

    printf("%d\n",fhq[y].maxn);

    rt=merge(merge(x,y),z);

}

int main(){

    scanf("%d%d",&n,&m);

    int op,l,r,v;

    for(int i=1;i<=n;i++){

        rt=merge(rt,newnode(0));

    }

    while(m--){

        scanf("%d%d%d",&op,&l,&r);

        if(op==1){

            scanf("%d",&v);

            add(l,r,v);

        }else if(op==2)reverse(l,r);

        else query(l,r);

    }

    return 0;

}