Splay

struct Splay
{
    #define ls(x) t[x].lson
    #define rs(x) t[x].rson
    #define fa(x) t[x].pre
    #define grafa(x) t[t[x].pre].pre
    static const int __=200005;

    struct node
    {
        int pre,lson,rson;
        ll val,minn,ad;
        int siz,rev;
        void set(int p,int v,int s)
        {
            val=minn=v,siz=s;
            pre=p,lson=-1,rson=-1,
            ad=0,rev=0;
        }
        void operator+=(const node &b)
        {
            siz+=b.siz;
            minn=min(minn,b.minn);
        }
        void putrev(){rev^=1;}
        void putadd(ll v)
        {
            val+=v,minn+=v,ad+=v;
        }
    }t[__];

    int root,idx;

    Splay():root(0),idx(0){t[0].set(-1,0,0);}

    void build(int a[],int n)
    {
        rs(0)=build(0,a,1,n);
    }

    int build(int pre,int a[],int l,int r)
    {
        if(l>r)return -1;
        int m=(l+r)>>1,x=++idx;
        t[x].set(pre,a[m],1);
        ls(x)=build(x,a,l,m-1);
        rs(x)=build(x,a,m+1,r);
        if(~ls(x))t[x]+=t[ls(x)];
        if(~rs(x))t[x]+=t[rs(x)];
        return x;
    }

    void pushup(int x)
    {
        t[x].siz=(x!=0);
        t[x].minn=t[x].val;
        if(~ls(x))t[x]+=t[ls(x)];
        if(~rs(x))t[x]+=t[rs(x)];
    }

    void zig(int x)
    {
        int y=fa(x);
        if(~fa(y))
            if(ls(fa(y))==y)
                ls(fa(y))=x;
            else rs(fa(y))=x;
        fa(x)=fa(y),fa(y)=x;
        ls(y)=rs(x);
        if(~ls(y))fa(ls(y))=y;
        rs(x)=y;
        if(fa(x)==-1)root=x;
        pushup(y),pushup(x);
    }

    void zag(int x)
    {
        int y=fa(x);
        if(~fa(y))
            if(ls(fa(y))==y)
                ls(fa(y))=x;
            else rs(fa(y))=x;
        fa(x)=fa(y),fa(y)=x;
        rs(y)=ls(x);
        if(~rs(y))fa(rs(y))=y;
        ls(x)=y;
        if(fa(x)==-1)root=x;
        pushup(y),pushup(x);
    }

    void splay(int x,int wz=-1)
    {
        while(x!=wz && fa(x)!=wz)
            if(grafa(x)==wz)
                if(ls(fa(x))==x)zig(x);
                else zag(x);
            else if(ls(fa(x))==x && ls(grafa(x))==fa(x))
                zig(fa(x)),zig(x);
            else if(rs(fa(x))==x && rs(grafa(x))==fa(x))
                zag(fa(x)),zag(x);
            else if(ls(fa(x))==x && rs(grafa(x))==fa(x))
                zig(x),zag(x);
            else if(rs(fa(x))==x && ls(grafa(x))==fa(x))
                zag(x),zig(x);
    }

    void pushdown(int x)
    {
        if(t[x].rev)
        {
            swap(ls(x),rs(x));
            if(ls(x)>0)t[ls(x)].putrev();
            if(rs(x)>0)t[rs(x)].putrev();
            t[x].rev=0;
        }
        if(t[x].ad)
        {
            ll &add=t[x].ad;
            if(ls(x)>0)t[ls(x)].putadd(add);
            if(rs(x)>0)t[rs(x)].putadd(add);
            add=0;
        }
    }

    int find_node(int wz)
    {
        int x=root;
        while(~x)
        {
            pushdown(x);
            int k=(x!=0);
            if(~ls(x))
                k+=t[ls(x)].siz;
            if(k==wz)return x;
            if(wz<k)x=ls(x);
            else wz-=k,x=rs(x);
        }
        return -1;
    }

    int get_min(int x)
    {
        for(pushdown(x);~ls(x);pushdown(x=ls(x)));
        return x;
    }

    //a[wz]后插入一个数val
    void insert(int wz,int val)
    {
        int x=find_node(wz);
        splay(x);
        if(rs(root)==-1)
        {
            rs(root)=++idx;
            t[idx].set(root,val,1);
            return;
        }
        int y=get_min(rs(root));
        splay(y,root);
        ls(rs(root))=++idx;
        t[idx].set(rs(root),val,1);
        pushup(rs(root)),pushup(root);
    }

    //删除a[wz]
    void erase(int wz)
    {
        int x=find_node(wz);
        splay(x);
        if(ls(x)==-1 && rs(x)==-1)
            root=-1;
        else if(ls(x)==-1)
        {
            root=rs(x),fa(rs(x))=-1;
            pushup(root);
        }
        else if(rs(x)==-1)
        {
            root=ls(x),fa(ls(x))=-1;
            pushup(root);
        }
        else
        {
            int y=get_min(rs(x));
            fa(ls(x))=y,ls(y)=ls(x);
            root=rs(x),fa(rs(x))=-1;
            pushup(y),pushup(root);
            splay(y);
        }
    }

    //a[l]……a[r] +val
    void add(int l,int r,ll val)
    {
        int le=find_node(l-1);
        int ri=find_node(r+1);
        splay(le),splay(ri,le);
        t[ls(rs(root))].putadd(val);
    }

    //a[l]……a[r] -> a[r]……a[l]
    void reversal(int l,int r)
    {
        int le=find_node(l-1);
        int ri=find_node(r+1);
        splay(le),splay(ri,le);
        t[ls(rs(root))].putrev();
    }

    //min(a[l]……a[r])
    ll get_min(int l,int r)
    {
        int le=find_node(l-1);
        int ri=find_node(r+1);
        splay(le),splay(ri,le);
        return t[ls(rs(root))].minn;
    }

    //a[l]……a[r] -> a[r-k+1]……a[r]a[l]……a[r-k]
    void revolve(int l,int r,int k)
    {
        k=(k%(r-l+1)+(r-l+1))%(r-l+1);
        if(!k)return;
        int le=find_node(l-1);
        int ri=find_node(r-k+1);
        splay(le),splay(ri,le);
        int x=ls(rs(root));
        int y=find_node(r);
        ls(rs(root))=-1;
        pushup(rs(root)),pushup(root);
        splay(y);
        int z=get_min(rs(root));
        splay(z,root);
        ls(rs(root))=x,fa(x)=rs(root);
        pushup(rs(root)),pushup(root);
    }

    void print(){dfs(root);}

    void dfs(int x)
    {
        if(x==-1)return;
        dfs(ls(x));
        printf("%d: pre:%d ls:%d rs:%d\n",x,fa(x),ls(x),rs(x));
        dfs(rs(x));
    }
}T;

题目链接:普通平衡树

splay:

#define ls(x) tree[x].lson
#define rs(x) tree[x].rson
#define fa(x) tree[x].pre
#define grafa(x) tree[tree[x].pre].pre

struct node
{
    int pre,lson,rson;
    int val,cont,siz;
    node(int pre=-1,int lson=-1,int rson=-1,
         int val=0,int cont=0,int siz=0):
        pre(pre),lson(lson),rson(rson),
        val(val),cont(cont),siz(siz) {}
} tree[100005];

int root=-1,idx=0;

void pushup(int x)
{
    tree[x].siz=tree[x].cont;
    if(~ls(x))
         tree[x].siz+=tree[ls(x)].siz;
    if(~rs(x))
         tree[x].siz+=tree[rs(x)].siz;
}

void zig(int x)
{
    int y=fa(x);
    if(~fa(y))
        if(ls(fa(y))==y)
            ls(fa(y))=x;
        else rs(fa(y))=x;
    fa(x)=fa(y),fa(y)=x;
    ls(y)=rs(x);
    if(~ls(y))fa(ls(y))=y;
    rs(x)=y;
    if(fa(x)==-1)root=x;
    pushup(y),pushup(x);
}

void zag(int x)
{
    int y=fa(x);
    if(~fa(y))
        if(ls(fa(y))==y)
            ls(fa(y))=x;
        else rs(fa(y))=x;
    fa(x)=fa(y),fa(y)=x;
    rs(y)=ls(x);
    if(~rs(y))fa(rs(y))=y;
    ls(x)=y;
    if(fa(x)==-1)root=x;
    pushup(y),pushup(x);
}

void splay(int x,int wz=-1)
{
    while(x!=wz && fa(x)!=wz)
    {
        if(grafa(x)==wz)
            if(ls(fa(x))==x)zig(x);
            else zag(x);
        else if(ls(fa(x))==x && ls(grafa(x))==fa(x))
            zig(fa(x)),zig(x);
        else if(rs(fa(x))==x && rs(grafa(x))==fa(x))
            zag(fa(x)),zag(x);
        else if(ls(fa(x))==x && rs(grafa(x))==fa(x))
            zig(x),zag(x);
        else if(rs(fa(x))==x && ls(grafa(x))==fa(x))
            zag(x),zig(x);
    }
}

int get_min(int x)
{
    while(~ls(x))x=ls(x);
    return x;
}

int get_max(int x)
{
    while(~rs(x))x=rs(x);
    return x;
}

int find_node(int val)
{
    int x=root;
    while(~x)
    {
        if(tree[x].val==val)
        {
            splay(x);
            return x;
        }
        if(val<tree[x].val)
            x=ls(x);
        else x=rs(x);
    }
    return -1;
}

int get_rank(int val)
{
    int res=1,x=root;
    while(~x)
        if(val<tree[x].val)
            x=ls(x);
        else
        {
            if(~ls(x))
                res+=tree[ls(x)].siz;
            if(tree[x].val==val)
            {
                splay(x);
                return res;
            }
            res+=tree[x].cont;
            x=rs(x);
        }
    return res;
}

int get_kth(int k)
{
    int x=root,y=-1;
    while(~x)
    {
        y=x;
        if(~ls(x) && k<=tree[ls(x)].siz)
            x=ls(x);
        else
        {
            int z=tree[x].cont;
            if(~ls(x))
                z+=tree[ls(x)].siz;
            if(k<=z)break;
            k-=z;
            x=rs(x);
        }
    }
    splay(y);
    return tree[y].val;
}
void insrt(int val)
{
    int x=root,y=find_node(val);
    if(~y)
    {
        tree[y].cont++;
        tree[y].siz++;
        return;
    }
    while(~x)
    {
        y=x;
        if(val<tree[x].val)
            x=ls(x);
        else x=rs(x);
    }
    x=++idx;
    tree[x]=node(y,-1,-1,val,1,1);
    if(y==-1)root=x;
    else
    {
        if(val<tree[y].val)
            ls(y)=x;
        else rs(y)=x;
        pushup(y),splay(x);
    }
}

int smaller(int val)
{
    int x=root,y=-1;
    while(~x)
    {
        if(val>tree[x].val && (y==-1 ||
        (~y && tree[x].val>tree[y].val)))
            y=x;
        if(val<=tree[x].val)x=ls(x);
        else x=rs(x);
    }
    splay(y);
    return tree[y].val;
}

int bigger(int val)
{
    int x=root,y=-1;
    while(~x)
    {
        if(val<tree[x].val && (y==-1 ||
        (~y && tree[x].val<tree[y].val)))
            y=x;
        if(val<tree[x].val)x=ls(x);
        else x=rs(x);
    }
    splay(y);
    return tree[y].val;
}

void delet(int val)
{
    int x=find_node(val);
    if(x==-1)return;
    if(tree[x].cont>1)
    {
        tree[x].cont--;
        tree[x].siz--;
        return;
    }
    if(ls(x)==-1 && rs(x)==-1)
        root=-1;
    else if(ls(x)==-1)
    {
        root=rs(x),fa(rs(x))=-1;
        pushup(root);
    }
    else if(rs(x)==-1)
    {
        root=ls(x),fa(ls(x))=-1;
        pushup(root);
    }
    else
    {
        int y=get_min(rs(x));
        fa(ls(x))=y,ls(y)=ls(x);
        root=rs(x),fa(rs(x))=-1;
        pushup(y),pushup(root);
        splay(y);
    }
}

int main()
{
    int q;
    scanf("%d",&q);
    while(q--)
    {
        int op,val;
        scanf("%d%d",&op,&val);
        if(op==1)insrt(val);
        if(op==2)delet(val);
        if(op==3)printf("%d\n",get_rank(val));
        if(op==4)printf("%d\n",get_kth(val));
        if(op==5)printf("%d\n",smaller(val));
        if(op==6)printf("%d\n",bigger(val));
    }
    return 0;
}

题目链接:文艺平衡树

区间翻转:

#define ls(x) tree[x].lson
#define rs(x) tree[x].rson
#define fa(x) tree[x].pre
#define grafa(x) tree[tree[x].pre].pre
 
struct node
{
    int pre,lson,rson;
    int siz,lazy;
    node(int pre=-1,int siz=0):
        pre(pre),siz(siz),
        lson(-1),rson(-1),lazy(0) {}
} tree[100005];
 
int root=-1,idx=-1;
 
void pushup(int x)
{
    tree[x].siz=(x!=0);
    if(~ls(x))tree[x].siz+=tree[ls(x)].siz;
    if(~rs(x))tree[x].siz+=tree[rs(x)].siz;
}
 
inline void zig(int x)
{
    int y=fa(x);
    if(~fa(y))
        if(ls(fa(y))==y)
            ls(fa(y))=x;
        else rs(fa(y))=x;
    fa(x)=fa(y),fa(y)=x;
    ls(y)=rs(x);
    if(~ls(y))fa(ls(y))=y;
    rs(x)=y;
    if(fa(x)==-1)root=x;
    pushup(y),pushup(x);
}
 
inline void zag(int x)
{
    int y=fa(x);
    if(~fa(y))
        if(ls(fa(y))==y)
            ls(fa(y))=x;
        else rs(fa(y))=x;
    fa(x)=fa(y),fa(y)=x;
    rs(y)=ls(x);
    if(~rs(y))fa(rs(y))=y;
    ls(x)=y;
    if(fa(x)==-1)root=x;
    pushup(y),pushup(x);
}
 
void splay(int x,int wz=-1)
{
    while(x!=wz && fa(x)!=wz)
        if(grafa(x)==wz)
            if(ls(fa(x))==x)zig(x);
            else zag(x);
        else if(ls(fa(x))==x && ls(grafa(x))==fa(x))
            zig(fa(x)),zig(x);
        else if(rs(fa(x))==x && rs(grafa(x))==fa(x))
            zag(fa(x)),zag(x);
        else if(ls(fa(x))==x && rs(grafa(x))==fa(x))
            zig(x),zag(x);
        else if(rs(fa(x))==x && ls(grafa(x))==fa(x))
            zag(x),zig(x);
}
 
void insrt(int wz)
{
    int x=root,y=-1;
    while(~x)
        if(wz<tree[y=x].siz)
            x=ls(x);
        else x=rs(x);
    x=++idx;
    tree[x]=node(y,1);
    if(y==-1)root=x;
    else
    {
        if(wz<tree[y].siz)
            ls(y)=x;
        else rs(y)=x;
        pushup(y),splay(x);
    }
}
 
inline void pushdown(int id)
{
    if(!tree[id].lazy)return;
    swap(ls(id),rs(id));
    tree[id].lazy=0;
    if(~ls(id))tree[ls(id)].lazy^=1;
    if(~rs(id))tree[rs(id)].lazy^=1;
}
 
int find_node(int wz)
{
    int x=root;
    while(~x)
    {
        pushdown(x);
        int k=(x!=0);
        if(~ls(x))
            k+=tree[ls(x)].siz;
        if(k==wz)return x;
        if(wz<k)x=ls(x);
        else wz-=k,x=rs(x);
    }
    return -1;
}
 
inline void reversal(int l,int r)
{
    int le=find_node(l-1);
    int ri=find_node(r+1);
    splay(le);
    splay(ri,le);
    int x=ls(rs(root));
    tree[x].lazy^=1;
}
 
void dfs(int x,int n)
{
    pushdown(x);
    if(~ls(x))dfs(ls(x),n);
    if(x!=0 && x!=n+1)
        printf("%d ",x);
    if(~rs(x))dfs(rs(x),n);
}
 
int main()
{
    int n,q;
    scanf("%d%d",&n,&q);
    for(int i=0; i<=n+1; i++)
        insrt(i);
    while(q--)
    {
        int l,r;
        scanf("%d%d",&l,&r);
        reversal(l,r);
    }
    dfs(root,n);
    return 0;
}

题目链接:Permutation Transformer

区间翻转/合并:

#define ls(x) tree[x].lson
#define rs(x) tree[x].rson
#define fa(x) tree[x].pre
#define grafa(x) tree[tree[x].pre].pre

struct node
{
    int pre,lson,rson;
    int siz,lazy;
    node(int pre=-1,int siz=0):
        pre(pre),siz(siz),
        lson(-1),rson(-1),lazy(0) {}
} tree[100005];

int root=-1,idx=-1;

void pushup(int x)
{
    tree[x].siz=(x!=0);
    if(~ls(x))tree[x].siz+=tree[ls(x)].siz;
    if(~rs(x))tree[x].siz+=tree[rs(x)].siz;
}

inline void zig(int x)
{
    int y=fa(x);
    if(~fa(y))
        if(ls(fa(y))==y)
            ls(fa(y))=x;
        else rs(fa(y))=x;
    fa(x)=fa(y),fa(y)=x;
    ls(y)=rs(x);
    if(~ls(y))fa(ls(y))=y;
    rs(x)=y;
    if(fa(x)==-1)root=x;
    pushup(y),pushup(x);
}

inline void zag(int x)
{
    int y=fa(x);
    if(~fa(y))
        if(ls(fa(y))==y)
            ls(fa(y))=x;
        else rs(fa(y))=x;
    fa(x)=fa(y),fa(y)=x;
    rs(y)=ls(x);
    if(~rs(y))fa(rs(y))=y;
    ls(x)=y;
    if(fa(x)==-1)root=x;
    pushup(y),pushup(x);
}

void splay(int x,int wz=-1)
{
    while(x!=wz && fa(x)!=wz)
        if(grafa(x)==wz)
            if(ls(fa(x))==x)zig(x);
            else zag(x);
        else if(ls(fa(x))==x && ls(grafa(x))==fa(x))
            zig(fa(x)),zig(x);
        else if(rs(fa(x))==x && rs(grafa(x))==fa(x))
            zag(fa(x)),zag(x);
        else if(ls(fa(x))==x && rs(grafa(x))==fa(x))
            zig(x),zag(x);
        else if(rs(fa(x))==x && ls(grafa(x))==fa(x))
            zag(x),zig(x);
}

void insrt(int wz)
{
    int x=root,y=-1;
    while(~x)
        if(wz<tree[y=x].siz)
            x=ls(x);
        else x=rs(x);
    x=++idx;
    tree[x]=node(y,1);
    if(y==-1)root=x;
    else
    {
        if(wz<tree[y].siz)
            ls(y)=x;
        else rs(y)=x;
        pushup(y),splay(x);
    }
}

inline void pushdown(int id)
{
    if(!tree[id].lazy)return;
    swap(ls(id),rs(id));
    tree[id].lazy=0;
    if(~ls(id))tree[ls(id)].lazy^=1;
    if(~rs(id))tree[rs(id)].lazy^=1;
}

int find_node(int wz)
{
    int x=root;
    while(~x)
    {
        pushdown(x);
        int k=(x!=0);
        if(~ls(x))
            k+=tree[ls(x)].siz;
        if(k==wz)return x;
        if(wz<k)x=ls(x);
        else wz-=k,x=rs(x);
    }
    return -1;
}

inline void reversal(int l,int r,int n)
{
    int le=find_node(l-1);
    int ri=find_node(r+1);
    splay(le),splay(ri,le);
    int x=ls(rs(root));
    ls(rs(root))=-1;
    pushup(rs(root)),pushup(root);
    tree[x].lazy^=1;
    int y=find_node(n-r+l-1);
    splay(y);
    ls(rs(root))=x,fa(x)=rs(root);
    pushup(rs(root)),pushup(root);

}

void dfs(int x,int n)
{
    pushdown(x);
    if(~ls(x))dfs(ls(x),n);
    if(x!=0 && x!=n+1)
        printf("%d\n",x);
    if(~rs(x))dfs(rs(x),n);
}

int main()
{
    int n,q;
    scanf("%d%d",&n,&q);
    for(int i=0;i<=n+1;i++)
        insrt(i);
    while(q--)
    {
        int l,r;
        scanf("%d%d",&l,&r);
        reversal(l,r,n);
    }
    dfs(root,n);
    return 0;
}

题目链接:Play with Chain

区间翻转/合并:

#define ls(x) tree[x].lson
#define rs(x) tree[x].rson
#define fa(x) tree[x].pre
#define grafa(x) tree[tree[x].pre].pre

struct node
{
    int pre,lson,rson;
    int siz,lazy;
    node(int pre=-1,int siz=0):
        pre(pre),siz(siz),
        lson(-1),rson(-1),lazy(0) {}
} tree[300005];

int root=-1,idx=-1;

void pushup(int x)
{
    tree[x].siz=(x!=0);
    if(~ls(x))tree[x].siz+=tree[ls(x)].siz;
    if(~rs(x))tree[x].siz+=tree[rs(x)].siz;
}

inline void zig(int x)
{
    int y=fa(x);
    if(~fa(y))
        if(ls(fa(y))==y)
            ls(fa(y))=x;
        else rs(fa(y))=x;
    fa(x)=fa(y),fa(y)=x;
    ls(y)=rs(x);
    if(~ls(y))fa(ls(y))=y;
    rs(x)=y;
    if(fa(x)==-1)root=x;
    pushup(y),pushup(x);
}

inline void zag(int x)
{
    int y=fa(x);
    if(~fa(y))
        if(ls(fa(y))==y)
            ls(fa(y))=x;
        else rs(fa(y))=x;
    fa(x)=fa(y),fa(y)=x;
    rs(y)=ls(x);
    if(~rs(y))fa(rs(y))=y;
    ls(x)=y;
    if(fa(x)==-1)root=x;
    pushup(y),pushup(x);
}

void splay(int x,int wz=-1)
{
    while(x!=wz && fa(x)!=wz)
        if(grafa(x)==wz)
            if(ls(fa(x))==x)zig(x);
            else zag(x);
        else if(ls(fa(x))==x && ls(grafa(x))==fa(x))
            zig(fa(x)),zig(x);
        else if(rs(fa(x))==x && rs(grafa(x))==fa(x))
            zag(fa(x)),zag(x);
        else if(ls(fa(x))==x && rs(grafa(x))==fa(x))
            zig(x),zag(x);
        else if(rs(fa(x))==x && ls(grafa(x))==fa(x))
            zag(x),zig(x);
}

void insrt(int val)
{
    int x=root,y=-1;
    while(~x)
        if(val<tree[y=x].siz)
            x=ls(x);
        else x=rs(x);
    x=++idx;
    tree[x]=node(y,1);
    if(y==-1)root=x;
    else
    {
        if(val<tree[y].siz)
            ls(y)=x;
        else rs(y)=x;
        pushup(y),splay(x);
    }
}

inline void pushdown(int id)
{
    if(!tree[id].lazy)return;
    swap(ls(id),rs(id));
    tree[id].lazy=0;
    if(~ls(id))tree[ls(id)].lazy^=1;
    if(~rs(id))tree[rs(id)].lazy^=1;
}

int find_node(int wz)
{
    int x=root;
    while(~x)
    {
        pushdown(x);
        int k=(x!=0);
        if(~ls(x))
            k+=tree[ls(x)].siz;
        if(k==wz)return x;
        if(wz<k)x=ls(x);
        else wz-=k,x=rs(x);
    }
    return -1;
}

inline void flip(int l,int r)
{
    int le=find_node(l-1);
    int ri=find_node(r+1);
    splay(le);
    splay(ri,le);
    int x=ls(rs(root));
    tree[x].lazy^=1;
}

int get_min(int x)
{
    pushdown(x);
    while(~ls(x))
    {
        x=ls(x);
        pushdown(x);
    }
    return x;
}

inline void cut(int l,int r,int k)
{
    int le=find_node(l-1);
    int ri=find_node(r+1);
    splay(le),splay(ri,le);
    int x=ls(rs(root));
    ls(rs(root))=-1;
    pushup(rs(root)),pushup(root);
    int y=find_node(k);
    splay(y);
    int z=get_min(rs(root));
    splay(z,root);
    ls(rs(root))=x,fa(x)=rs(root);
    pushup(rs(root)),pushup(root);
}

bool flag;

void dfs(int x,int n)
{
    pushdown(x);
    if(~ls(x))dfs(ls(x),n);
    if(x!=0 && x!=n+1)
    {
        if(flag)printf(" ");
        printf("%d",x);
        flag=true;
    }
    if(~rs(x))dfs(rs(x),n);
}

void init(void)
{
    flag=false;
    root=idx=-1;
    memset(tree,-1,sizeof(tree));
}

int main()
{
    int n,q;
    while(~scanf("%d%d",&n,&q) && ~n)
    {
        init();
        for(int i=0; i<=n+1; i++)
            insrt(i);
        char op[5];
        int x,y,z;
        while(q--)
        {
            scanf("%s%d%d",op,&x,&y);
            if(op[0]=='C')
            {
                scanf("%d",&z);
                cut(x,y,z);
            }
            if(op[0]=='F')flip(x,y);
        }
        dfs(root,n);
        printf("\n");
    }
    return 0;
}

题目链接:Splay

区间删除:

#define ls(x) tree[x].lson
#define rs(x) tree[x].rson
#define fa(x) tree[x].pre
#define grafa(x) tree[tree[x].pre].pre

struct node
{
    int pre,lson,rson;
    int val,cont,siz;
    node(int pre=-1,int lson=-1,int rson=-1,
         int val=0,int cont=0,int siz=0):
        pre(pre),lson(lson),rson(rson),
        val(val),cont(cont),siz(siz) {}
} tree[200005];

int root=-1,idx=-1;

void pushup(int x)
{
    tree[x].siz=tree[x].cont;
    if(!x)tree[x].siz=0;
    if(~ls(x))
         tree[x].siz+=tree[ls(x)].siz;
    if(~rs(x))
         tree[x].siz+=tree[rs(x)].siz;
}

void zig(int x)
{
    int y=fa(x);
    if(~fa(y))
        if(ls(fa(y))==y)
            ls(fa(y))=x;
        else rs(fa(y))=x;
    fa(x)=fa(y),fa(y)=x;
    ls(y)=rs(x);
    if(~ls(y))fa(ls(y))=y;
    rs(x)=y;
    if(fa(x)==-1)root=x;
    pushup(y),pushup(x);
}

void zag(int x)
{
    int y=fa(x);
    if(~fa(y))
        if(ls(fa(y))==y)
            ls(fa(y))=x;
        else rs(fa(y))=x;
    fa(x)=fa(y),fa(y)=x;
    rs(y)=ls(x);
    if(~rs(y))fa(rs(y))=y;
    ls(x)=y;
    if(fa(x)==-1)root=x;
    pushup(y),pushup(x);
}

void splay(int x,int wz=-1)
{
    while(x!=wz && fa(x)!=wz)
    {
        if(grafa(x)==wz)
            if(ls(fa(x))==x)zig(x);
            else zag(x);
        else if(ls(fa(x))==x && ls(grafa(x))==fa(x))
            zig(fa(x)),zig(x);
        else if(rs(fa(x))==x && rs(grafa(x))==fa(x))
            zag(fa(x)),zag(x);
        else if(ls(fa(x))==x && rs(grafa(x))==fa(x))
            zig(x),zag(x);
        else if(rs(fa(x))==x && ls(grafa(x))==fa(x))
            zag(x),zig(x);
    }
}

int get_min(int x)
{
    while(~ls(x))x=ls(x);
    return x;
}

int get_max(int x)
{
    while(~rs(x))x=rs(x);
    return x;
}

int find_node(int val)
{
    int x=root;
    while(~x)
    {
        if(tree[x].val==val)
        {
            splay(x);
            return x;
        }
        if(val<tree[x].val)
            x=ls(x);
        else x=rs(x);
    }
    return -1;
}

void insrt(int val)
{
    int x=root,y=find_node(val);
    if(~y)
    {
        tree[y].cont++;
        tree[y].siz++;
        return;
    }
    while(~x)
    {
        y=x;
        if(val<tree[x].val)
            x=ls(x);
        else x=rs(x);
    }
    x=++idx;
    tree[x]=node(y,-1,-1,val,1,1);
    if(!x)tree[x].siz=0;
    if(y==-1)root=x;
    else
    {
        if(val<tree[y].val)
            ls(y)=x;
        else rs(y)=x;
        pushup(y),splay(x);
    }
}

int small_equel(int val)
{
    int x=root,y=-1;
    while(~x)
    {
        if(tree[x].val<=val && (y==-1 ||
        (~y && tree[x].val>tree[y].val)))
            y=x;
        if(val<=tree[x].val)x=ls(x);
        else x=rs(x);
    }
    splay(y);
    return tree[y].val;
}

int smaller(int val,int wz=-1)
{
    int x=root,y=-1;
    while(~x)
    {
        if(tree[x].val<val && (y==-1 ||
        (~y && tree[x].val>tree[y].val)))
            y=x;
        if(val<=tree[x].val)x=ls(x);
        else x=rs(x);
    }
    splay(y,wz);
    return y;
}

int bigger(int val,int wz=-1)
{
    int x=root,y=-1;
    while(~x)
    {
        if(tree[x].val>val && (y==-1 ||
        (~y && tree[x].val<tree[y].val)))
            y=x;
        if(val<tree[x].val)x=ls(x);
        else x=rs(x);
    }
    splay(y,wz);
    return y;
}

void delet(int l,int r)
{
    bigger(r,smaller(l));
    ls(rs(root))=-1;
    pushup(rs(root));
    pushup(root);
}

int main()
{
    insrt(-1),insrt(1e9+7);
    int T;
    scanf("%d",&T);
    while(T--)
    {
        char op[2];
        scanf("%s",op);
        if(op[0]=='I')
        {
            int x;
            scanf("%d",&x);
            insrt(x);
        }
        if(op[0]=='Q')
        {
            int x;
            scanf("%d",&x);
            printf("%d\n",small_equel(x));
        }
        if(op[0]=='D')
        {
            int l,r;
            scanf("%d%d",&l,&r);
            delet(l,r);
        }
    }
    return 0;
}

题目链接:Splay

区间加/删除询问区间和:

#define ls(x) tree[x].lson
#define rs(x) tree[x].rson
#define fa(x) tree[x].pre
#define grafa(x) tree[tree[x].pre].pre

struct node
{
    int pre,lson,rson,id,siz;
    ll val,sum,lazy;
    node(int a=-1,int b=-1,int c=-1,int d=0,
         int e=0,ll f=0,ll g=0,ll h=0):
        pre(a),lson(b),rson(c),id(d),
        siz(e),val(f),sum(g),lazy(h) {}
} tree[200005];

int root=-1,idx=-1;

void pushup(int x)
{
    tree[x].sum=tree[x].val;
    tree[x].siz=(x!=0);
    if(~ls(x))
    {
        tree[x].sum+=tree[ls(x)].sum;
        tree[x].siz+=tree[ls(x)].siz;
    }
    if(~rs(x))
    {
        tree[x].sum+=tree[rs(x)].sum;
        tree[x].siz+=tree[rs(x)].siz;
    }
}

void zig(int x)
{
    int y=fa(x);
    if(~fa(y))
        if(ls(fa(y))==y)
            ls(fa(y))=x;
        else rs(fa(y))=x;
    fa(x)=fa(y),fa(y)=x;
    ls(y)=rs(x);
    if(~ls(y))fa(ls(y))=y;
    rs(x)=y;
    if(fa(x)==-1)root=x;
    pushup(y),pushup(x);
}

void zag(int x)
{
    int y=fa(x);
    if(~fa(y))
        if(ls(fa(y))==y)
            ls(fa(y))=x;
        else rs(fa(y))=x;
    fa(x)=fa(y),fa(y)=x;
    rs(y)=ls(x);
    if(~rs(y))fa(rs(y))=y;
    ls(x)=y;
    if(fa(x)==-1)root=x;
    pushup(y),pushup(x);
}

void splay(int x,int wz=-1)
{
    while(x!=wz && fa(x)!=wz)
        if(grafa(x)==wz)
            if(ls(fa(x))==x)zig(x);
            else zag(x);
        else if(ls(fa(x))==x && ls(grafa(x))==fa(x))
            zig(fa(x)),zig(x);
        else if(rs(fa(x))==x && rs(grafa(x))==fa(x))
            zag(fa(x)),zag(x);
        else if(ls(fa(x))==x && rs(grafa(x))==fa(x))
            zig(x),zag(x);
        else if(rs(fa(x))==x && ls(grafa(x))==fa(x))
            zag(x),zig(x);
}

inline void pushdown(int id)
{
    if(!tree[id].lazy)return;
    ll add=tree[id].lazy;
    if(~ls(id))
    {
        tree[ls(id)].val+=add;
        tree[ls(id)].lazy+=add;
        tree[ls(id)].sum+=tree[ls(id)].siz*add;
    }
    if(~rs(id))
    {
        tree[rs(id)].val+=add;
        tree[rs(id)].lazy+=add;
        tree[rs(id)].sum+=tree[rs(id)].siz*add;
    }
    tree[id].lazy=0;
    pushup(id);
}

void insrt(int id,ll val)
{
    int x=root,y=-1;
    while(~x)
    {
        pushdown(y=x);
        if(id<tree[x].id)
            x=ls(x);
        else x=rs(x);
    }
    x=++idx;
    tree[x]=node(y,-1,-1,id,1,val,val);
    if(y==-1)root=x;
    else
    {
        if(id<tree[y].id)
            ls(y)=x;
        else rs(y)=x;
        pushup(y),splay(x);
    }
}

int smaller(int id,int wz=-1)
{
    int x=root,y=-1;
    while(~x)
    {
        pushdown(x);
        if(tree[x].id<=id && (y==-1 ||
        (~y && tree[x].id>tree[y].id)))
            y=x;
        if(id<=tree[x].id)x=ls(x);
        else x=rs(x);
    }
    splay(y,wz);
    return y;
}

int bigger(int id,int wz=-1)
{
    int x=root,y=-1;
    while(~x)
    {
        pushdown(x);
        if(tree[x].id>=id && (y==-1 ||
        (~y && tree[x].id<tree[y].id)))
            y=x;
        if(id<tree[x].id)x=ls(x);
        else x=rs(x);
    }
    splay(y,wz);
    return y;
}

ll get_sum(int l,int r)
{
    bigger(r+1,smaller(l-1));
    return tree[ls(rs(root))].sum;
}

void add(int l,int r,ll val)
{
    bigger(r+1,smaller(l-1));
    int x=ls(rs(root));
    tree[x].val+=val;
    tree[x].lazy+=val;
    tree[x].sum+=tree[x].siz*val;
    pushdown(rs(root));
    pushup(root);
}

void delet(int l,int r)
{
    bigger(r+1,smaller(l-1));
    ls(rs(root))=-1;
    pushup(rs(root));
    pushup(root);
}

int main()
{
    int q;
    insrt(0,0),insrt(100000005,0);
    scanf("%d",&q);
    while(q--)
    {
        char op[2];
        int x,y;
        scanf("%s%d%d",op,&x,&y);
        x=min(max(1,x),100000000);
        y=min(max(1,y),100000000);
        if(op[0]=='I')insrt(x,(ll)y);
        if(op[0]=='Q')printf("%lld\n",get_sum(x,y));
        if(op[0]=='D')delet(x,y);
        if(op[0]=='M')
        {
            ll z;
            scanf("%lld",&z);
            add(x,y,z);
        }
    }
    return 0;
}

最后编辑于：2018.08.16 16:15:44

人面猴
序言：七十年代末，一起剥皮案震惊了整个滨河市，随后出现的几起案子，更是在滨河造成了极大的恐慌，老刑警刘岩，带你破解...
沈念sama阅读 217,734评论 6赞 505
死咒
序言：滨河连续发生了三起死亡事件，死亡现场离奇诡异，居然都是意外死亡，警方通过查阅死者的电脑和手机，发现死者居然都...
沈念sama阅读 92,931评论 3赞 394
救了他两次的神仙让他今天三更去死
文/潘晓璐我一进店门，熙熙楼的掌柜王于贵愁眉苦脸地迎上来，“玉大人，你说我怎么就摊上这事。” “怎么了？”我有些...
开封第一讲书人阅读 164,133评论 0赞 354
道士缉凶录：失踪的卖姜人
文/不坏的土叔我叫张陵，是天一观的道长。经常有香客问我，道长，这世上最难降的妖魔是什么？我笑而不...
开封第一讲书人阅读 58,532评论 1赞 293
港岛之恋（遗憾婚礼）
正文为了忘掉前任，我火速办了婚礼，结果婚礼上，老公的妹妹穿的比我还像新娘。我一直安慰自己，他们只是感情好，可当我...
茶点故事阅读 67,585评论 6赞 392
恶毒庶女顶嫁案：这布局不是一般人想出来的
文/花漫我一把揭开白布。她就那样静静地躺着，像睡着了一般。火红的嫁衣衬着肌肤如雪。梳的纹丝不乱的头发上，一...
开封第一讲书人阅读 51,462评论 1赞 302
城市分裂传说
那天，我揣着相机与录音，去河边找鬼。笑死，一个胖子当着我的面吹牛，可吹牛的内容都是我干的。我是一名探鬼主播，决...
沈念sama阅读 40,262评论 3赞 418
双鸳鸯连环套：你想象不到人心有多黑
文/苍兰香墨我猛地睁开眼，长吁一口气：“原来是场噩梦啊……” “哼！你这毒妇竟也来了？” 一声冷哼从身侧响起，我...
开封第一讲书人阅读 39,153评论 0赞 276
万荣杀人案实录
序言：老挝万荣一对情侣失踪，失踪者是张志新（化名）和其女友刘颖，没想到半个月后，有当地人在树林里发现了一具尸体，经...
沈念sama阅读 45,587评论 1赞 314
护林员之死
正文独居荒郊野岭守林人离奇死亡，尸身上长有42处带血的脓包…… 初始之章·张勋以下内容为张勋视角年9月15日...
茶点故事阅读 37,792评论 3赞 336
白月光启示录
正文我和宋清朗相恋三年，在试婚纱的时候发现自己被绿了。大学时的朋友给我发了我未婚夫和他白月光在一起吃饭的照片。...
茶点故事阅读 39,919评论 1赞 348
活死人
序言：一个原本活蹦乱跳的男人离奇死亡，死状恐怖，灵堂内的尸体忽然破棺而出，到底是诈尸还是另有隐情，我是刑警宁泽，带...
沈念sama阅读 35,635评论 5赞 345
日本核电站爆炸内幕
正文年R本政府宣布，位于F岛的核电站，受9级特大地震影响，放射性物质发生泄漏。R本人自食恶果不足惜，却给世界环境...
茶点故事阅读 41,237评论 3赞 329
男人毒药：我在死后第九天来索命
文/蒙蒙一、第九天我趴在偏房一处隐蔽的房顶上张望。院中可真热闹，春花似锦、人声如沸。这庄子的主人今日做“春日...
开封第一讲书人阅读 31,855评论 0赞 22
一桩弑父案，背后竟有这般阴谋
文/苍兰香墨我抬头看了看天上的太阳。三九已至，却和暖如春，着一层夹袄步出监牢的瞬间，已是汗流浃背。一阵脚步声响...
开封第一讲书人阅读 32,983评论 1赞 269
情欲美人皮
我被黑心中介骗来泰国打工，没想到刚下飞机就差点儿被人妖公主榨干…… 1. 我叫王不留，地道东北人。一个月前我还...
沈念sama阅读 48,048评论 3赞 370
代替公主和亲
正文我出身青楼，却偏偏与公主长得像，于是被迫代替她去往敌国和亲。传闻我的和亲对象是个残疾皇子，可洞房花烛夜当晚...
茶点故事阅读 44,864评论 2赞 354

Splay

题目链接:普通平衡树

splay:

题目链接:文艺平衡树

区间翻转:

题目链接:Permutation Transformer

区间翻转/合并:

题目链接:Play with Chain

区间翻转/合并:

题目链接:Splay

区间删除:

题目链接:Splay

区间加/删除 询问区间和:

推荐阅读更多精彩内容

区间加/删除询问区间和: