首页 > > 程序设计 > C/C++ >

bzoj1251 -- splay

2018-06-17 23:16:08来源：未知阅读 ()

splay模板题。

用splay维护序列，令splay的中序遍历为这个序列，则在处理[l,r]时，先将l-1旋转到根，再将r+1旋转到根的右子树，那么根的右子树的左子树就是[l,r]了。

代码：

#include<iostream>
#include<cstdio>
#include<cstring>
using namespace std;
#define N 50010
#define INF 2147483647
bool b[N];
int i,j,k,m,n,c[N],s[N],a[N],Rt,p[N],ch[N][2],f[N],x,y,z;
inline int Get(int x){return ch[f[x]][1]==x;}
inline int _Max(int x,int y){return x>y?x:y;}
inline void Up(int x){
    c[x]=_Max(a[x],_Max(c[ch[x][0]],c[ch[x][1]]));
    s[x]=s[ch[x][0]]+s[ch[x][1]]+1;
}
inline void Down(int x){
    if(!x)return;
    if(p[x]){
        if(ch[x][0])p[ch[x][0]]+=p[x],c[ch[x][0]]+=p[x],a[ch[x][0]]+=p[x];
        if(ch[x][1])p[ch[x][1]]+=p[x],c[ch[x][1]]+=p[x],a[ch[x][1]]+=p[x];
        p[x]=0;
    }
    if(b[x]){
        int t=ch[x][0];ch[x][0]=ch[x][1];ch[x][1]=t;
        if(ch[x][0])b[ch[x][0]]^=1;
        if(ch[x][1])b[ch[x][1]]^=1;
        b[x]=0;
    }
}
inline void Rotate(int x){
    int y=f[x];bool d=Get(x);
    ch[f[y]][Get(y)]=x;
    f[x]=f[y];
    ch[y][d]=ch[x][d^1];
    f[ch[y][d]]=y;
    ch[x][d^1]=y;
    f[y]=x;Up(y);
}
inline void P(int x,int g){
    if(f[x]!=g)P(f[x],g);
    Down(x);
}
inline void Splay(int x,int g){
    P(x,g);
    while(f[x]!=g){
        if(f[f[x]]){
            if(f[f[x]]==g){Rotate(x);break;}
            Rotate(Get(x)==Get(f[x])?f[x]:x);
        }
        Rotate(x);
    }
    Up(x);
    if(!g)Rt=x;
}
inline int Search(int x){
    int u=Rt;
    Down(u);
    while(s[ch[u][0]]!=x){
        if(s[ch[u][0]]>x)u=ch[u][0];else x-=s[ch[u][0]]+1,u=ch[u][1];
        Down(u);
    }
    return u;
}
inline int Build(int l,int r){
    if(l>r)return 0;
    if(l==r)return l;
    int Mid=l+r>>1;
    ch[Mid][0]=Build(l,Mid-1);
    ch[Mid][1]=Build(Mid+1,r);
    s[Mid]=s[ch[Mid][0]]+s[ch[Mid][1]]+1;
    f[ch[Mid][0]]=f[ch[Mid][1]]=Mid;
    Up(Mid);
    return Mid;
}
inline void Update(int l,int r,int x){
    int u=Search(l-1),v=Search(r+1);
    Splay(u,0);Splay(v,u);
    c[ch[v][0]]+=x;
    p[ch[v][0]]+=x;
    a[ch[v][0]]+=x;
}
inline void Reverse(int l,int r){
    int u=Search(l-1),v=Search(r+1);
    Splay(u,0);Splay(v,u);
    b[ch[v][0]]^=1;
}
inline int Query(int l,int r){
    int u=Search(l-1),v=Search(r+1);
    Splay(u,0);Splay(v,u);
    return c[ch[v][0]];
}
inline void Init(){
    for(int i=1;i<=n+2;i++)s[i]=1;
    c[0]=a[0]=-INF;c[1]=a[1]=-INF;
    c[n+2]=a[n+2]=-INF;
    Rt=Build(1,n+2);
    ch[0][0]=Rt;
}
int main()
{
    scanf("%d%d",&n,&m);
    Init();
    while(m--){
        scanf("%d",&k);
        if(k==1)scanf("%d%d%d",&x,&y,&z),Update(x,y,z);else{
            scanf("%d%d",&x,&y);
            if(k==2)Reverse(x,y);else printf("%d\n",Query(x,y));
        }
    }
    return 0;
}