题解 P4146 【序列终结者】

· · 题解

通过平衡树来维护区间操作的一道比较像模板的题目。

看见楼上的几位大佬用的都是splay，补一发fhq_treap的题解好了。

#include<cstdio>
#include<iostream>
#define ls(x) t[x].ch[0]
#define rs(x) t[x].ch[1]
using namespace std;

struct node{
    int size,key,val,cx,add,tur,ch[2],maxn;
}t[100010];
//size:子树大小 key:随机生成的key值 val:当前位置的值 cx:在数组中的位置（好像后面没用到？） add:加法的延迟标记 tur:旋转的延迟标记 ch：左右儿子（用ls（x）与rs（x）表示） maxn:区间的最大值 
int n,m,gs,rt;
int seed=623; 
int com,l,r,zhi;

inline int rand(){
    return seed=(int)((seed*1000000007ll)%0x7fffffff);
}
//从下向上推时，需要同时更新两个值：最大值与子树大小 
inline void push_up(int x){
    t[x].size=t[ls(x)].size+t[rs(x)].size+1;
    t[x].maxn=t[x].val;
    //防止在最大值为负值时访问到空节点（空节点处最大值为0） 
    if(ls(x))t[x].maxn=max(t[x].maxn,t[ls(x)].maxn);
    if(rs(x))t[x].maxn=max(t[x].maxn,t[rs(x)].maxn);
}
//向下推同样需要维护两个值：加的lazy标记与旋转的lazy标记 
inline void push_down(int x){
    if(t[x].tur){
        if(ls(x))t[ls(x)].tur^=1;
        if(rs(x))t[rs(x)].tur^=1;
        ls(x)^=rs(x)^=ls(x)^=rs(x);
        t[x].tur=0;
    }
    if(t[x].add){
        if(ls(x)){//防止给0节点加上奇奇怪怪的值 
            t[ls(x)].add+=t[x].add;
            t[ls(x)].val+=t[x].add;
            t[ls(x)].maxn+=t[x].add;
        }
        if(rs(x)){
            t[rs(x)].add+=t[x].add;
            t[rs(x)].val+=t[x].add;
            t[rs(x)].maxn+=t[x].add;
        }
        t[x].add=0;
        update(x);
    }
}
//正常的分离/合并 
int merge(int x,int y){
    int now;
    push_down(x);push_down(y);
    if(!x || !y)return x|y;
    if(t[x].key<t[y].key){
        now=x,rs(x)=merge(t[x].ch[1],y);
    }
    else now=y,ls(y)=merge(x,t[y].ch[0]);
    push_up(now);
    return now;
}

void split(int root,int bz,int &x,int &y){
    if(!root){x=y=0;return;}
    push_down(root);
    if(t[ls(root)].size>=bz)y=root,split(ls(root),bz,x,ls(y));
    else x=root,split(rs(root),bz-t[ls(root)].size-1,rs(x),y);
    push_up(root);
}

inline void insert(int x){
    t[++gs].key=rand();
    t[gs].val=x;
    t[gs].cx=gs;
    t[gs].maxn=x;
    t[gs].size=1;
    rt=merge(rt,gs);
}
//对l-r这段区间进行操作时，只需要先把l-r这段区间单独分离出来，再在分出来的区间的根节点上加lazy标记即可 
inline void update1(int l,int r,int zhi){
    int x,y,z;
    split(rt,l-1,x,y);
    split(y,r-l+1,y,z);
    t[y].maxn+=zhi;
    t[y].add+=zhi;
    t[y].val+=zhi;
    rt=merge(merge(x,y),z);
}

inline void update2(int l,int r){
    int x,y,z;
    split(rt,l-1,x,y);
    split(y,r-l+1,y,z);
    t[y].tur^=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",t[y].maxn);
    rt=merge(merge(x,y),z);
}

int main(){
    scanf("%d %d",&n,&m); 
    for(int i=1;i<=n;i++){
        insert(0);
    }
    while(m--){
        scanf("%d",&com);
        if(com==1){scanf("%d %d %d",&l,&r,&zhi),update1(l,r,zhi);}
        else if(com==2){scanf("%d %d",&l,&r),update2(l,r);}
        else if(com==3){scanf("%d %d",&l,&r),query(l,r);}
    }
    return 0;
}