精华内容
下载资源
问答
  • 无旋Treap——从入门到放弃

    千次阅读 2017-09-22 15:53:27
    但是本文并不打算给大家讲无旋Treap复杂度证明一类的。 很显然每次操作都是期望Olog(n)的{\bf O}\log(n)的什么是Treap?Treap=Tree+heap 其核心思想在于在权值上维护一棵二叉查找树,在优先级上维护一个堆 有旋...

    前言

    已经是从入门到放弃的第四篇了。
    但是本文并不打算给大家讲无旋Treap复杂度证明一类的。
    很显然每次操作都是期望Olog(n)

    什么是Treap?

    Treap=Tree+heap
    其核心思想在于在权值上维护一棵二叉查找树,在优先级上维护一个堆
    有旋treap利用旋转操作来维护堆的性质,
    而无旋treap利用有序构树维护堆的性质。

    无旋Treap的两大构树顺序:权值与原排列

    权值构树是很常见的一种构树方法。和有旋treap一样,左儿子与右儿子分别表示比自己小或比自己大的树,同时其优先级均低于该节点。这类问题用有旋treap也能够很好地解决。这样的题有很多,比如bzoj3224普通平衡树
    但很不幸的是,很多与平衡树沾边的题目大多有维护一个原有有序序列的要求,这个要求基本上就把有旋treap干掉了。但是对于无旋treap,我们可以按原有的序列进行构树,这样就可以维护一个原有的有序排列了。

    无旋treap的核心操作:split与merge

    但是在构树之后肯定是有修改操作的。这点是毋庸置疑的。对于有旋treap,我们可以通过旋转来插入要加入的权值或是删除对应的节点,但对于可能需要进行区间操作的无旋treap,我们显然不能直接这样做。
    此时,因为无旋treap的有序性,我们可以像一般的有旋treap一样对需要
    插入/删除的部分进行定位查找。
    如果是对于权值有序,像普通的有旋treap一样直接递归查找即可,
    如果是对于原序列有序,则维护一组指针,也可以很方便地进行查询。
    那么在查询到了相应的树中位置之后,我们需要做的就是——
    把这棵树拆开

    split

    整个无旋treap的核心就是它的有序性。
    在找到了需要操作的位置后,我们可以把这棵树拆成两棵有序的树。
    对于查询到的节点,我们根据该节点左儿子的大小对这个节点应该在哪棵树进行判断,然后递归处理即可。

    inline D split(Treap* pos,int k){
        if(pos==NULL) return D(NULL,NULL);
        D y;
        if(sze(pos->son[0])>=k){
            y=split(pos->son[0],k);
            pos->son[0]=y.second;
            pos->update();
            y.second=pos;
        }else{
            y=split(pos->son[1],k-1-sze(pos->son[0]));
            pos->son[1]=y.first;
            pos->update();
            y.first=pos;
        }
        return y;
    }

    merge

    在你进行了加入/删除操作之后,你发现你手上现在有两到三棵树了,自然我们需要将这些树合并。合并的具体操作也是递归处理,此时就可以维护无旋treap的堆性质。
    但是需要注意的是,合并时两棵树的左右位置,维护的是整棵树的有序性。

    inline Treap* merge(Treap* a,Treap* b){
        if(!a) return b;
        if(!b) return a;
        if(a->weight<b->weight){
            a->son[1]=merge(a->son[1],b);
            a->update();
            return a;
        }else{
            b->son[0]=merge(a,b->son[0]);
            b->update();
            return b;
        }
    }

    水得如壶口瀑布一样的水题

    (1)bzoj3224:普通平衡树
    题面见链接 传送门
    最简单最基础的权值排序外加单点修改查询

    #include<iostream>
    #include<cstdio>
    #include<cstdlib>
    #include<cstring>
    #include<string>
    #include<ctime>
    #include<cmath>
    #include<algorithm>
    #include<cctype>
    #include<iomanip>
    using namespace std;
    inline int read(){
        int i=0,f=1;
        char ch;
        for(ch=getchar();!isdigit(ch);ch=getchar())
            if(ch=='-') f=-1;
        for(;isdigit(ch);ch=getchar())
            i=(i<<3)+(i<<1)+(ch^48);
        return i*f;
    }
    int buf[1024];
    inline void write(int x){
        if(!x){putchar('0');return ;}
        if(x<0){putchar('-');x=-x;}
        while(x){buf[++buf[0]]=x%10,x/=10;}
        while(buf[0]) putchar(buf[buf[0]--]+48);
        return ;
    }
    struct Treap{
        Treap* son[2];
        int weight,sze,data;
        Treap(int v){
            sze=1,data=v;weight=rand();
            son[1]=son[0]=NULL;
            return ;
        }
        inline void update(){
            sze=1+(son[0]!=NULL?son[0]->sze:0)+(son[1]!=NULL?son[1]->sze:0);
            return ;
        }
    }*root;
    typedef pair<Treap*,Treap*>D;
    inline int sze(Treap* pos){
        return pos?pos->sze:0;
    }
    int n,ord,x;
    inline Treap* merge(Treap* a,Treap* b){
        if(!a) return b;
        if(!b) return a;
        if(a->weight<b->weight){
            a->son[1]=merge(a->son[1],b);
            a->update();
            return a;
        }else{
            b->son[0]=merge(a,b->son[0]);
            b->update();
            return b;
        }
    }
    inline D split(Treap* pos,int k){
        if(pos==NULL) return D(NULL,NULL);
        D y;
        if(sze(pos->son[0])>=k){
            y=split(pos->son[0],k);
            pos->son[0]=y.second;
            pos->update();
            y.second=pos;
        }else{
            y=split(pos->son[1],k-1-sze(pos->son[0]));
            pos->son[1]=y.first;
            pos->update();
            y.first=pos;
        }
        return y;
    }
    inline int getrank(Treap* pos,int x){
        if(pos==NULL) return 0;
        else return (pos->data>=x)?getrank(pos->son[0],x):getrank(pos->son[1],x)+1+sze(pos->son[0]);
    }
    inline int getkth(int k){
        D x=split(root,k-1);
        D y=split(x.second,1);
        Treap* pos=y.first;
        root=merge(x.first,merge(pos,y.second));
        return pos==NULL?0:pos->data;
    }
    inline void insert(int d){
        int k=getrank(root,d);
        D x=split(root,k);
        Treap* pos=new Treap(d);
        root=merge(x.first,merge(pos,x.second));
        return ;
    }
    inline void remove(int d){
        int k=getrank(root,d);
        D x=split(root,k);
        D y=split(x.second,1);
        root=merge(x.first,y.second);
        return ;
    }
    signed main(){
        n=read();
        for(int i=1;i<=n;++i){
            ord=read();x=read();
            switch(ord){
                case 1:insert(x);break;
                case 2:remove(x);break;
                case 3:write(getrank(root,x)+1);puts("");break;
                case 4:write(getkth(x));puts("");break;
                case 5:write(getkth(getrank(root,x)));puts("");break;
                case 6:write(getkth(getrank(root,x+1)+1));puts("");break;
            }
        }
        return 0;
    }

    (2)bzoj1503 郁闷的出纳员
    题面依然见链接点这里
    很明显你不能直接进行全局修改对伐。这个时候你需要打一个差分。

    #include<iostream>
    #include<cstdio>
    #include<cstdlib>
    #include<cstring>
    #include<string>
    #include<ctime>
    #include<cmath>
    #include<algorithm>
    #include<cctype>
    #include<iomanip>
    using namespace std;
    inline int read(){
        int i=0,f=1;
        char ch;
        for(ch=getchar();!isdigit(ch);ch=getchar())
            if(ch=='-') f=-1;
        for(;isdigit(ch);ch=getchar())
            i=(i<<3)+(i<<1)+(ch^48);
        return i*f;
    }
    int buf[1024];
    inline void write(int x){
        if(!x){putchar('0');return ;}
        if(x<0){putchar('-');x=-x;}
        while(x){buf[++buf[0]]=x%10,x/=10;}
        while(buf[0]) putchar(buf[buf[0]--]+48);
        return ;
    }
    #define stan 11
    struct Treap{
        Treap* son[2];
        int sze,val,weight;
        Treap(){val=sze=0,weight=rand();son[1]=son[0]=NULL;}
        inline void update(){
            sze=1+son[0]->sze+son[1]->sze;
        }
    }*null=new Treap,*root=null;
    typedef pair<Treap*,Treap*> D;
    int m,mini,tmp=0,x,cnt;
    char ord[stan];
    inline Treap* newtreap(int x){
        Treap* pos=new Treap();
        pos->son[0]=pos->son[1]=null;
        pos->sze=1;pos->val=x;
        return pos;
    }
    inline Treap* merge(Treap* a,Treap* b){
        if(a==null) return b;
        if(b==null) return a;
        if(a->weight<b->weight){
            a->son[1]=merge(a->son[1],b);
            a->update();
            return a;
        }else{
            b->son[0]=merge(a,b->son[0]);
            b->update();
            return b;
        }
    }
    inline D split(Treap* pos,int k){
        if(pos==null) return D(null,null);
        D y;
        if(pos->son[0]->sze>=k){
            y=split(pos->son[0],k);
            pos->son[0]=y.second;
            pos->update();
            y.second=pos;
        }else{
            y=split(pos->son[1],k-1-pos->son[0]->sze);
            pos->son[1]=y.first;
            pos->update();
            y.first=pos;
        }
        return y;
    }
    inline int getrank(Treap* pos,int x){
        if(pos==null) return 0;
        return (pos->val>=x)?getrank(pos->son[0],x):getrank(pos->son[1],x)+1+pos->son[0]->sze;
    }
    inline int getkth(int k){
        D x=split(root,k-1);
        D y=split(x.second,1);
        Treap* pos=y.first;
        root=merge(x.first,merge(pos,y.second));
        return pos->val;
    }
    inline void insert(int d){
        int k=getrank(root,d);
        D x=split(root,k);
        Treap* pos=newtreap(d);
        root=merge(x.first,merge(pos,x.second));
        return ;
    }
    inline void remove(){
        D x=split(root,1);
        root=x.second;
        ++cnt;
        return ;
    }
    signed main(){
        m=read();mini=read();
        while(m--){
            scanf("%s",ord);x=read();
            switch(ord[0]){
                case 'I':if(x>=mini) insert(x-tmp);break;
                case 'F':{
                    if(root==null||root->sze<x)
                        puts("-1");
                    else{
                        write(getkth(root->sze-x+1)+tmp);
                        puts("");
                    }
                    break;
                }
                case 'A':tmp+=x;break;
                case 'S':{
                    tmp-=x;
                    while(root!=null&&getkth(1)+tmp<mini)
                        remove();
                    break;
                }
            }
        }
        write(cnt);
        return 0;
    }

    (3)bzoj3223文艺平衡树
    题面照例见链接点我点我
    基础的区间翻转操作,像线段树一样打标记即可

    #include<iostream>
    #include<cstdio>
    #include<cstdlib>
    #include<cstring>
    #include<string>
    #include<ctime>
    #include<cmath>
    #include<algorithm>
    #include<cctype>
    #include<iomanip>
    using namespace std;
    inline int read(){
        int i=0,f=1;
        char ch;
        for(ch=getchar();!isdigit(ch);ch=getchar())
            if(ch=='-') f=-1;
        for(;isdigit(ch);ch=getchar())
            i=(i<<3)+(i<<1)+(ch^48);
        return i*f;
    }
    int buf[1024];
    inline void write(int x){
        if(!x){putchar('0');return ;}
        if(x<0){putchar('-');x=-x;}
        while(x){buf[++buf[0]]=x%10,x/=10;}
        while(buf[0]) putchar(buf[buf[0]--]+48);
        return ;
    }
    #define stan 555555
    struct Treap{
        Treap* son[2];
        int val,weight,sze;bool flip; 
        Treap(){
            val=-999999999;sze=0;weight=rand();flip=false;
            return ;
        }
        inline void update(){
            sze=son[1]->sze+son[0]->sze+1;
            return ;
        }
    }*null=new Treap(),*root=null,*stack[stan],*x,*last;
    typedef pair<Treap*,Treap*> D;
    int n,m,sta,en;
    inline void maintain_flip(Treap* pos){
        if(pos==null) return ;
        pos->flip^=1;
        return ;
    }
    inline void pushdown(Treap* pos){
        if(pos==null) return ;
        if(pos->flip){
            pos->flip^=1;
            maintain_flip(pos->son[0]);
            maintain_flip(pos->son[1]);
            swap(pos->son[0],pos->son[1]);
        }
        return ;
    }
    inline Treap* newtreap(int val){
        Treap *pos=new Treap();
        pos->son[1]=pos->son[0]=null;pos->weight=rand();
        pos->val=val;pos->sze=1;pos->flip=0;
        return pos;
    }
    inline Treap* merge(Treap* a,Treap* b){
        if(a==null) return b;
        if(b==null) return a;
        pushdown(a);pushdown(b);
        if(a->weight<b->weight){
            a->son[1]=merge(a->son[1],b);
            a->update();
            return a;
        }else{
            b->son[0]=merge(a,b->son[0]);
            b->update();
            return b;
        }
    }
    inline D split(Treap* pos,int k){
        if(pos==null) return D(null,null);
        D y;pushdown(pos);
        if(pos->son[0]->sze>=k){
            y=split(pos->son[0],k);
            pos->son[0]=y.second;
            pos->update();
            y.second=pos;
        }else{
            y=split(pos->son[1],k-1-pos->son[0]->sze);
            pos->son[1]=y.first;
            pos->update();
            y.first=pos;
        }
        return y;
    }
    inline Treap* build(){
        int p=0;
        for(int i=1;i<=n;++i){
            x=newtreap(i);last=null;
            while(p&&stack[p]->weight>x->weight){
                stack[p]->update();
                last=stack[p];
                stack[p--]=null;
            }
            if(p) stack[p]->son[1]=x;
            x->son[0]=last;stack[++p]=x;
        }
        while(p) stack[p--]->update();
        return stack[1];
    }
    inline void reverse(){
        sta=read();en=read();
        D x=split(root,sta-1);
        D y=split(x.second,en-sta+1);
        maintain_flip(y.first);
        root=merge(x.first,merge(y.first,y.second));
        return ;
    }
    inline void write_in_order(Treap* pos){
        if(pos==null) return;
        pushdown(pos);
        write_in_order(pos->son[0]);
        write(pos->val);putchar(' ');
        write_in_order(pos->son[1]);
        return ;
    }
    signed main(){
        n=read();m=read();
        root=build();
        while(m--) reverse();
        write_in_order(root); 
        return 0;
    }

    (4)ZJOI2006书架
    题面还是点链接吧http://www.lydsy.com/JudgeOnline/problem.php?id=1861
    这个地方也是很正常的单点修改,不过注意一下合并的顺序即可

    #include<iostream>
    #include<cstdio>
    #include<cstdlib>
    #include<cstring>
    #include<string>
    #include<ctime>
    #include<cmath>
    #include<algorithm>
    #include<cctype>
    #include<iomanip>
    using namespace std;
    inline int read(){
        int i=0,f=1;
        char ch;
        for(ch=getchar();!isdigit(ch);ch=getchar())
            if(ch=='-') f=-1;
        for(;isdigit(ch);ch=getchar())
            i=(i<<3)+(i<<1)+(ch^48);
        return i*f;
    }
    int buf[1024];
    inline void write(int x){
        if(!x){putchar('0');return ;}
        if(x<0){putchar('-');x=-x;}
        while(x){buf[++buf[0]]=x%10,x/=10;}
        while(buf[0]) putchar(buf[buf[0]--]+48);
        return ;
    }
    typedef unsigned int uint;
    inline uint nextUint() {
        static uint seed = 19260817;
        seed ^= seed << 13;
        seed ^= seed >> 17;
        seed ^= seed << 5;
        return seed;
    }
    #define stan 88888
    #define sten 11
    struct Treap{
        Treap* son[2];
        Treap* fa;
        int sze,val;
        uint weight;
        Treap(){val=-999999999,sze=0,weight=nextUint(),son[0]=son[1]=fa=this;}
        inline void update(){
            sze=son[0]->sze+son[1]->sze+1;
            son[0]->fa=son[1]->fa=this;
        }
    }*null=new Treap(),*root=null,*stack[stan],*x,*last,*posi[stan];
    typedef pair<Treap*,Treap*> D;
    int n,m,s,u,a[stan];
    char ord[sten];
    inline Treap* newtreap(int val){
        Treap* pos=new Treap();
        pos->son[1]=pos->son[0]=pos->fa=null;
        pos->sze=1;pos->val=val;pos->weight=nextUint();
        return pos;
    }
    inline Treap* merge(Treap* a,Treap* b){
        if(a==null) return b;
        if(b==null) return a;
        if(a->weight<b->weight){
            a->son[1]=merge(a->son[1],b);
            a->update();
            return a;
        }else{
            b->son[0]=merge(a,b->son[0]);
            b->update();
            return b;
        }
    }
    inline D split(Treap* pos,int k){
        if(pos==null) return D(null,null);
        D y;
        if(pos->son[0]->sze>=k){
            y=split(pos->son[0],k);
            pos->son[0]=y.second;
            pos->update();
            y.second=pos;
        }else{
            y=split(pos->son[1],k-1-pos->son[0]->sze);
            pos->son[1]=y.first;
            pos->update();
            y.first=pos;
        }
        return y;
    }
    inline Treap* build(){
        int p=0;
        for(int i=1;i<=n;++i){
            a[i]=read();
            posi[a[i]]=x=newtreap(a[i]);last=null;
            while(p&&stack[p]->weight>x->weight){
                stack[p]->update();
                last=stack[p];
                stack[p--]=null;
            }
            if(p) stack[p]->son[1]=x;x->fa=stack[p];
            x->son[0]=last;last->fa=x;
            stack[++p]=x;
        }
        while(p) stack[p--]->update();
        return stack[1];
    }
    inline int getrank(Treap* pos){
        int ret=pos->son[0]->sze;
        while(pos->fa!=null&&pos->fa!=NULL){
            if(pos==pos->fa->son[1]) ret+=pos->fa->son[0]->sze+1;
            pos=pos->fa;
        }
        return ret;
    }
    inline void addhead(int x){
        int k=getrank(posi[x]);
        D X=split(root,k);
        D y=split(X.second,1);
        root=merge(y.first,merge(X.first,y.second));
        return ;
    }
    inline void addtail(int x){
        int k=getrank(posi[x]);
        D X=split(root,k);
        D y=split(X.second,1);
        root=merge(X.first,merge(y.second,y.first));
        return ;
    }
    void addmid(int xxx,int opt) {  
        if(!opt) return ;
        static D X,y,z;  
        int k=getrank(posi[xxx]);  
        X=split(root, k);  
        y=split(X.second,1);  
        if(opt==-1)X=split(X.first,X.first->sze-1), root=merge(merge(X.first,y.first),merge(X.second,y.second));  
        else z=split(y.second,1), root=merge(merge(X.first,z.first),merge(y.first,z.second));  
    }  
    inline int getkth(int k){
        D X=split(root,k-1);
        D y=split(X.second,1);
        Treap* pos=y.first;
        root=merge(X.first,merge(pos,y.second));
        return pos->val;
    }
    signed main(){
        n=read();m=read();
        root=build();
        while(m--){
            scanf("%s",ord);s=read();
            switch(ord[0]){
                case 'T':addhead(s);break;
                case 'B':addtail(s);break;
                case 'I':u=read();addmid(s,u);break;
                case 'A':write(getrank(posi[s]));puts("");break;
                case 'Q':write(getkth(s));puts("");break;
            }
        }
        return 0;
    }

    (5)CQOI2014排序机械臂
    题面还是有链接就是这里
    很中规中矩的不固定排列序+区间修改

    #include<iostream>
    #include<cstdio>
    #include<cstdlib>
    #include<cstring>
    #include<string>
    #include<ctime>
    #include<cmath>
    #include<algorithm>
    #include<cctype>
    #include<iomanip>
    using namespace std;
    inline int read(){
        int i=0,f=1;
        char ch;
        for(ch=getchar();!isdigit(ch);ch=getchar())
            if(ch=='-') f=-1;
        for(;isdigit(ch);ch=getchar())
            i=(i<<3)+(i<<1)+(ch^48);
        return i*f;
    }
    int buf[1024];
    inline void write(int x){
        if(!x){putchar('0');return ;}
        if(x<0){putchar('-');x=-x;}
        while(x){buf[++buf[0]]=x%10,x/=10;}
        while(buf[0]) putchar(buf[buf[0]--]+48);
        return ;
    }
    typedef unsigned int uint;
    inline uint nxtunit(){
        static uint seed=19260817;
        seed^=seed<<13;
        seed^=seed>>17;
        seed^=seed<<5;
        return seed;
    }
    #define stan 111111
    struct Treap{
        Treap* son[2];
        Treap* fa;
        int sze,val;
        uint weight;
        bool flip;
        Treap(){val=-999999999,sze=0,weight=nxtunit(),son[0]=son[1]=fa=this;flip=false;}
        inline void update(){
            sze=son[0]->sze+son[1]->sze+1;
            son[0]->fa=son[1]->fa=this;
        }
    }*null=new Treap(),*root=null,*stack[stan],*x,*last,*posi[stan];
    typedef pair<Treap*,Treap*> D;
    int n,m,s,u,a[stan],to[stan];
    struct thing{
        int ord,val;
    }thi[stan];
    inline bool cmp(const thing &a,const thing &b){
        if(a.val!=b.val) return a.val<b.val;
        else return a.ord<b.ord;
    }
    inline Treap* newtreap(int val){
        Treap* pos=new Treap();
        pos->son[1]=pos->son[0]=pos->fa=null;
        pos->sze=1;pos->val=val;pos->weight=nxtunit();
        pos->flip=false;
        return pos;
    }
    inline void pushdown(Treap* pos){
        if(pos==null||pos==NULL) return ;
        if(pos->flip){
            pos->flip^=1;
            pos->son[0]->flip^=1;
            pos->son[1]->flip^=1;
            swap(pos->son[0],pos->son[1]);
        }
        return ;
    }
    inline Treap* merge(Treap* a,Treap* b){
        if(a==null) return b;
        if(b==null) return a;
        pushdown(a);pushdown(b);
        if(a->weight<b->weight){
            a->son[1]=merge(a->son[1],b);
            a->update();
            return a;
        }else{
            b->son[0]=merge(a,b->son[0]);
            b->update();
            return b;
        }
    }
    inline D split(Treap* pos,int k){
        if(pos==null) return D(null,null);
        D y;pushdown(pos);
        if(pos->son[0]->sze>=k){
            y=split(pos->son[0],k);
            pos->son[0]=y.second;
            pos->update();
            y.second=pos;
        }else{
            y=split(pos->son[1],k-1-pos->son[0]->sze);
            pos->son[1]=y.first;
            pos->update();
            y.first=pos;
        }
        return y;
    }
    inline void rotate(Treap* pos){
        if(pos==null||pos==NULL) return ;
        rotate(pos->fa);
        pushdown(pos);
        return ; 
    }
    inline int getrank(Treap* pos){
        rotate(pos);
        int ret=pos->son[0]->sze+1;
        while(pos->fa!=null&&pos->fa!=NULL){
            if(pos==pos->fa->son[1]) ret+=pos->fa->son[0]->sze+1;
            pos=pos->fa;
        }
        return ret;
    }
    inline int getans(int d){
        int ret=getrank(posi[d]);
        D x=split(root,ret);
        D y=split(x.first,d-1);
        y.second->flip^=1;
        root=merge(merge(y.first,y.second),x.second);
        return ret;
    }
    signed main(){
        n=read();
        for(int i=1;i<=n;++i){
            a[i]=read();thi[i].ord=i;thi[i].val=a[i];
        }
        sort(thi+1,thi+n+1,cmp);
        for(int i=1;i<=n;++i)
            to[thi[i].ord]=i;
        for(int i=1;i<=n;++i){
            posi[to[i]]=newtreap(a[i]);
            root=merge(root,posi[to[i]]);
        }
        for(int i=1;i<n;++i){
            write(getans(i));
            putchar(' ');
        }
        write(getans(n));
        return 0;
    }

    (6) NOI2005维修数列
    题面在这里
    如果你上面五道题都A了,这个题也不难想
    写就是另一回事了

    #include<iostream>
    #include<cstdio>
    #include<cstdlib>
    #include<cstring>
    #include<string>
    #include<ctime>
    #include<cmath>
    #include<algorithm>
    #include<cctype>
    #include<iomanip>
    using namespace std;
    inline int read(){
        int i=0,f=1;
        char ch;
        for(ch=getchar();!isdigit(ch);ch=getchar())
            if(ch=='-') f=-1;
        for(;isdigit(ch);ch=getchar())
            i=(i<<3)+(i<<1)+(ch^48);
        return i*f;
    }
    int buf[1024];
    inline void write(int x){
        if(!x){putchar('0');return ;}
        if(x<0){putchar('-');x=-x;}
        while(x){buf[++buf[0]]=x%10,x/=10;}
        while(buf[0]) putchar(buf[buf[0]--]+48);
        return ;
    }
    #define stan 555555
    struct Treap{
        Treap* son[2];
        int val,weight,sze,sum,l,r,m;bool flip,mark; 
        Treap(){val=l=r=m=-999999999,sum=sze=0;mark=flip=0;weight=rand();}
        inline void update(){
            sze=son[1]->sze+son[0]->sze+1;
            sum=son[1]->sum+son[0]->sum+val;
            l=max(son[0]->l,max(son[0]->sum+val,son[0]->sum+val+son[1]->l));
            r=max(son[1]->r,max(son[1]->sum+val,son[1]->sum+val+son[0]->r));
            m=max(son[0]->m,max(max(0,son[0]->r)+val+max(0,son[1]->l),son[1]->m));
        }
    }*null=new Treap(),*root=null,*stack[stan],*x,*last;
    typedef pair<Treap*,Treap*> D;
    int n,m,a[stan];
    char ord[stan];
    inline void maintain_flip(Treap* pos){
        if(pos==null) return ;
        pos->flip^=1;swap(pos->l,pos->r);
        return ;
    }
    inline void maintain_mark(Treap* pos,int c){
        if(pos==null) return ;
        pos->val=c;pos->sum=pos->sze*c;
        pos->l=pos->r=pos->m=max(pos->sze*c,c);
        pos->mark=true;
        return ;
    }
    inline void pushdown(Treap *pos){
        if(pos==null) return ;
        if(pos->flip){
            pos->flip^=1;
            maintain_flip(pos->son[0]);
            maintain_flip(pos->son[1]);
            swap(pos->son[0],pos->son[1]);
        }
        if(pos->mark){
            maintain_mark(pos->son[0],pos->val);
            maintain_mark(pos->son[1],pos->val);
            pos->mark=0;
        }
        return ;
    }
    inline Treap* newtreap(int val)
    {
        Treap *pos=new Treap();
        pos->son[1]=pos->son[0]=null;pos->weight=rand();
        pos->val=pos->sum=val;pos->sze=1;pos->flip=pos->mark=0;
        pos->m=pos->l=pos->r=val;
        return pos;
    }
    Treap* merge(Treap* a,Treap* b){
        if(a==null) return b;
        if(b==null) return a;
        pushdown(a);pushdown(b);
        if(a->weight<b->weight){
            a->son[1]=merge(a->son[1],b);
            a->update();
            return a;
        }else{
            b->son[0]=merge(a,b->son[0]);
            b->update();
            return b;
        }
    }
    D split(Treap* pos,int k){
        if(pos==null) return D(null,null);
        D y;pushdown(pos);
        if(pos->son[0]->sze>=k){
            y=split(pos->son[0],k);
            pos->son[0]=y.second;
            pos->update();
            y.second=pos;
        }else{
            y=split(pos->son[1],k-1-pos->son[0]->sze);
            pos->son[1]=y.first;
            pos->update();
            y.first=pos;
        }
        return y;
    }
    inline Treap* build(){
        int p=0;
        for(int i=1;i<=n;++i){
            a[i]=read();
            x=newtreap(a[i]);last=null;
            while(p&&stack[p]->weight>x->weight){
                stack[p]->update();
                last=stack[p];
                stack[p--]=null;
            }
            if(p) stack[p]->son[1]=x;
            x->son[0]=last;stack[++p]=x;
        }
        while(p) stack[p--]->update();
        return stack[1];
    }
    inline void adjust(Treap *pos){
        if(pos==null) return;
        if(pos->son[0]!=null) adjust(pos->son[0]);
        if(pos->son[1]!=null) adjust(pos->son[1]);
        delete pos;return ;
    }
    inline void insert(){
        int sta;sta=read();n=read();
        Treap* pos=build();
        D x=split(root,sta);
        root=merge(x.first,merge(pos,x.second));
        return ;
    }
    inline void remove(){
        int sta;sta=read();n=read();
        D x=split(root,sta-1);
        D y=split(x.second,n);
        adjust(y.first);
        root=merge(x.first,y.second);
        return ;
    }
    inline void reverse(){
        int sta;sta=read();n=read();
        D x=split(root,sta-1);
        D y=split(x.second,n);
        maintain_flip(y.first);
        root=merge(x.first,merge(y.first,y.second));
        return ;
    }
    inline void make_same(){
        int sta,c;sta=read();n=read();c=read();
        D x=split(root,sta-1);
        D y=split(x.second,n);
        maintain_mark(y.first,c);
        root=merge(x.first,merge(y.first,y.second));
        return ;
    }
    inline int get_sum(){
        int sta;sta=read();n=read();
        if(n==0) return 0;
        D x=split(root,sta-1);
        D y=split(x.second,n);
        int ret=y.first->sum;
        root=merge(x.first,merge(y.first,y.second));
        return ret;
    }
    signed main(){
        n=read();m=read();
        root=build();
        while(m--){
            scanf("%s",ord);
            switch(ord[0]){
                case 'I':{insert();break;}
                case 'D':{remove();break;}
                case 'M':{
                    if(ord[2]=='K'){make_same();break;}
                    else {write(root->m);puts("");break;}
                }
                case 'G':{write(get_sum());puts("");break;}
                case 'R':{reverse();break;}
            }
        } 
        return 0;
    }

    小结

    终于是又水了一篇
    其实我觉得LadyLex的讲解才是坠吼的传送门
    %%%LadyLex
    同时感谢Xehoth大佬在看到我在内网莫名血T之后甩给了我一个强大的随机数生成器
    %%%Xehoth

    展开全文
  • Treap

    2018-05-24 11:10:29
    Treap Treap是一种动态平衡的BST(Binary Search ...可以证明Treap中插入,删除和查找的期望时间复杂度均为O(logn)。优先级利用随机,从而保持Treap相对平衡。一般我们用Treap就是用来替代平衡二叉排序树用的。 ...

    Treap

            Treap是一种动态平衡的BST(Binary Search Tree),它每个节点拥有键值和优先级两种属性。对于键值而言,它是一颗排序二叉树。对于优先级而言,这棵树是堆(优先级最高的是根节点)。可以证明Treap中插入,删除和查找的期望时间复杂度均为O(logn)。优先级利用随机,从而保持Treap相对平衡。

    一般我们用Treap就是用来替代平衡二叉排序树用的。

             Treap实现的代码很少,实现简单。我们可以在Treap的基础上实现名次树。

             名次树支持两个操作:

            1)找出第k小的元素(元素从小到大排序的第k个)。(区间问题还是主席树吧)

            2)找到值x的名次。

    Treap基本代码:

    #include<cstdio>
    #include<cstring>
    #include<cstdlib>
    using namespace std;
    
    struct Node
    {
        Node *ch[2];
        int r;//优先级,构成大顶堆
        int v;//键值,构成排序二叉树
    
        int cmp(int x)//比较键值大小
        {
            if(x==v) return -1;
            return x<v?0:1;
        }
    };
    
    //d=0表示左旋,d=1表示右旋
    void rotate(Node* &o,int d)
    {
        Node *k=o->ch[d^1];
        o->ch[d^1]=k->ch[d];
        k->ch[d]=o;
        o=k;
    }
    
    //插入值为x的节点
    void insert(Node* &o,int x)
    {
        if(o==NULL)
        {
            o=new Node();
            o->ch[0]=o->ch[1]=NULL;
            o->v=x;
            o->r=rand();//在cstdlib头声明
        }
        else
        {
            //如这里改成int d=o->cmp(x);
            //就不可以插入相同的值,因为d可能为-1
            int d=x<(o->v)?0:1;
            insert(o->ch[d],x);
            if(o->ch[d]->r > o->r)
                rotate(o,d^1);
        }
    }
    
    //删除v值为x的节点
    void remove(Node *&o,int v)
    {
        if(o==NULL) return ;//空时返回
    
        int d=o->cmp(v);
        if(d==-1)//o就是需要删除的节点
        {
            Node *u=o;
            if(o->ch[0] && o->ch[1])
            {
                int d2 = o->ch[0]->r < o->ch[1]->r ?0:1;
                rotate(o,d2);
                remove(o->ch[d2],v);
            }
            else
            {
                if(o->ch[0]==NULL)o=o->ch[1];
                else o=o->ch[0];
                delete u;//记得删除节点
            }
        }
        else remove(o->ch[d],v);
    }
    int find(Node *o,int x)
    {
        while(o)
        {
            int d=o->cmp(x);
            if(d==-1)return 1; //存在
            o=o->ch[d];
        }
        return 0;              //不存在
    }
    
    

    Treap实现名次树的代码:

    #include<cstdio>
    #include<cstring>
    #include<cstdlib>
    #include<cassert>
    using namespace std;
    struct Node
    {
        Node *ch[2];
        int r,v,s;//s表示节点数
    
        Node(int v):v(v)
        {
            ch[0]=ch[1]=NULL;
            r=rand();//在cstdlib头声明
            s=1;
        }
    
        int cmp(int x)
        {
            if(x==v)return -1;
            return x<v?0:1;
        }
        void maintain()
        {
            s=1;
            if(ch[0]!=NULL) s+=ch[0]->s;
            if(ch[1]!=NULL) s+=ch[1]->s;
        }
    };
    void rotate(Node* &o,int d)
    {
        Node *k=o->ch[d^1];
        o->ch[d^1]=k->ch[d];
        k->ch[d]=o;
        o->maintain();
        k->maintain();
        o=k;
    }
    void insert(Node* &o,int x)//o子树中事先不存在x
    {
        if(o==NULL) o=new Node(x);
        else
        {
            //如这里改成int d=o->cmp(x);
            //就不可以插入相同的值,因为d可能为-1
            int d=x<(o->v)?0:1;
            insert(o->ch[d],x);
            if(o->ch[d]->r > o->r)
                rotate(o,d^1);
        }
        o->maintain();
    }
    
    void remove(Node* &o,int x)
    {
        if(o==NULL) return ;//空时返回
    
        int d=o->cmp(x);
        if(d==-1)
        {
            Node *u=o;
            if(o->ch[0] && o->ch[1])
            {
                int d2=(o->ch[0]->r < o->ch[1]->r)?0:1;
                rotate(o,d2);
                remove(o->ch[d2],x);
            }
            else
            {
                if(o->ch[0]==NULL) o=o->ch[1];
                else o=o->ch[0];
                delete u;//这个要放里面
            }
        }
        else remove(o->ch[d],x);
        if(o) o->maintain();//之前o存在,但是删除节点后o可能就是空NULL了,所以需要先判断o是否为空
    }
    
    //返回关键字从小到大排序时的第k个值
    int kth(Node* o,int k)
    {
        assert(o && k>=1 && k<=o->s);//保证输入合法
        int s=(o->ch[0]==NULL)?0:o->ch[0]->s;
        if(k==s+1) return o->v;
        else if(k<=s) return kth(o->ch[0],k);
        else return kth(o->ch[1],k-s-1);
    }
    
    //返回值x在树中的排名,就算x不在o树中也能返回排名
    //返回值范围在[1,o->s+1]范围内
    int rank(Node* o,int x)
    {
        if(o==NULL) return 1;//未找到x;
    
        int num= o->ch[0]==NULL ? 0:o->ch[0]->s;
        if(x==o->v) return num+1;
        else if(x < o->v) return rank(o->ch[0],x);
        else return rank(o->ch[1],x)+num+1;
    }
    
    
    int main()
    {
        int n=0;
        while(scanf("%d",&n)==1 && n)
        {
            Node *root=NULL;
            for(int i=0;i<n;i++)
            {
                int x;
                scanf("%d",&x);
                if(root==NULL) root=new Node(x);
                else insert(root,x);
            }
    
            int v;
            while(scanf("%d",&v)==1)
            {
                printf("%d\n",rank(root,v));
            }
        }
        return 0;
    }
    
    

    展开全文
  • Treap模版

    2015-01-10 13:54:35
    为了准备省选,终于学了平衡树(Treap),晚上的资源很多,这里只对Treap做一些简单...经过严格的数学证明,可以证明时间复杂度为O(lgn),这里不再给出。 每在BST中加入一个节点,就随机分配一个fix值,如果此时不满足最

    为了准备省选,终于学了平衡树(Treap),晚上的资源很多,这里只对Treap做一些简单介绍

    顾名思义Treap=tree+heap,具体来说就是节点的value值是一棵二叉查找树,fix值是一个小根堆。由于fix是随机分配的,可以看作Treap是随机平衡的。经过严格的数学证明,可以证明时间复杂度为O(lgn),这里不再给出。

    每在BST中加入一个节点,就随机分配一个fix值,如果此时不满足最小堆性质,就通过左旋(或右旋)来调整为最小堆。给出一张图(转)


    删除节点时则通过左旋、右旋至某一只有一个儿子节点或叶节点上,删除即可。

    求前驱,后继,排名等方法同BST,不再赘述。 模版如下:

    (操作1,插入值为num的节点;操作2,删除值为num的节点;操作3,查询num的排名;操作4,查询排名为num的数;操作5,求num的前驱;操作6,求num的后继;操作7,求最小值;操作8,求最大值;merge操作此处无用,为合并两棵treap;)

    #include<cstdio>
    #include<cstring>
    #include<iostream>
    #include<cstdlib>
    #include<ctime>
    using namespace std;
    struct treap_node{
    	treap_node *left,*right;
    	int val,fix,size,wgt;
    	treap_node(int val): val(val)  {left=right=NULL; size=wgt=1; fix=rand();}
    	int lsize()
    	  {
    	    if (left)
    	      return left->size;
    	    else 
    	      return 0;
    	  }
    	int rsize()
    	  {
    	    if (right)
    	      return right->size;
    	    else 
    	      return 0;
    	  }
    	void Maintain()
    	  {
    	    size=wgt;
    	    size+=lsize()+rsize();
    	  }
    };
    int n;
    treap_node *root;
    void tlr(treap_node *&a)
    {
    	treap_node *b=a->right;
    	a->right=b->left;
    	b->left=a;
    	a->Maintain();
    	b->Maintain();
    	a=b;
    }
    void trr(treap_node *&a)
    {
    	treap_node *b=a->left;
    	a->left=b->right;
    	b->right=a;
    	a->Maintain();
    	b->Maintain();
    	a=b;
    }
    void insert(treap_node *&p,int value)
    {
    	if (!p)
    	  p=new treap_node(value);
    	else
    	  {
    	    if (value==p->val)
    	      p->wgt++;
    	    if (value<p->val)
    	      {
    	        insert(p->left,value);
    	        if (p->left->fix<p->fix)
    	          trr(p);
    	      }
    	    if (value>p->val)
    	      {
    	        insert(p->right,value);
    	        if (p->right->fix<p->fix)
    	          tlr(p);
    	      }
    	  }
    	p->Maintain();
    }
    void del(treap_node *&p,int value)
    {
    	if (value==p->val)
    	  {
    	    if (p->wgt==1)
    	      {
    	        if (!p->left||!p->right)
    	          {
    	            if (!p->left)
    	              p=p->right;
    	            else
    	              p=p->left;
    	          }
    	        else
    	          {
    	            if (p->left->fix<p->right->fix)
    	              {
    	                trr(p);
    	                del(p->right,value);
    	              }
    	            else
    	              {
    	                tlr(p);
    	                del(p->left,value);
    	              }
    	          }
    	      }
    	    else
    	      p->wgt--;
    	  }
    	else
    	  {
    	    if (value<p->val)
    	      del(p->left,value);
    	    else
    	      del(p->right,value);
    	  }
    	if (p!=NULL) p->Maintain();
    }
    treap_node* tpred(treap_node *&p,int value,treap_node* best)
    {
    	if (!p) return best;
    	if (p->val<value)
    	  return tpred(p->right,value,p);
    	else
    	  return tpred(p->left,value,best);
    } 
    treap_node* tsucc(treap_node *&p,int value,treap_node* best)
    {
    	if (!p) return best;
    	if (p->val>value)
    	  return tsucc(p->left,value,p);
        else
    	  return tsucc(p->right,value,best); 
    }
    treap_node* kth(treap_node *&p,int k)
    {
    	if (k<p->lsize()+1)
    	  return kth(p->left,k);
    	else
    	  if (k>p->lsize()+p->wgt)
    	    return kth(p->right,k-p->lsize()-p->wgt);
    	  else
    	    return p;
    }
    int rank(treap_node *&p,int value,int cur)
    {
    	if (value==p->val)
    	  return cur+p->lsize()+1;
    	else
    	  if (value<p->val)
    	    return rank(p->left,value,cur);
          else
            return rank(p->right,value,cur+p->lsize()+p->wgt);
    }
    void merge(treap_node *&a,treap_node *&b)
    {
    	if (a->left) merge(a->left,b);
    	if (a->right) merge(a->right,b);
    	insert(b,a->val);
    }
    int main()
    {
    	int i,kind,num,k;
    	treap_node *null=NULL;
    	srand(time(0)); k=0;
    	scanf("%d",&n);
    	for (i=1;i<=n;++i)
    	  {
    	  	scanf("%d",&kind);
    	  	if (kind==1)
    	  	  {
    	  	  	k++;
    	  	    scanf("%d",&num);
    	  	    insert(root,num);
    	      }
    	  	if (kind==2)
    	  	  {
    	  	  	k--;
    	        scanf("%d",&num);
    	  	    del(root,num);
    	      }
    	  	if (kind==3)
    	  	  {
    	  	    scanf("%d",&num);
    	  	    printf("%d\n",rank(root,num,0));
    	      }
    	  	if (kind==4)
    		  {
    		  	scanf("%d",&num);
    		    treap_node *t;
    		    t=kth(root,num);
    		    printf("%d\n",t->val);
    		  }  
    		if (kind==5)
    		  {
    		  	scanf("%d",&num);
    		    treap_node *t;
    		    t=tpred(root,num,null);
    		    printf("%d\n",t->val);
    		  }
    		if (kind==6)
    		  {
    		  	scanf("%d",&num);
    		    treap_node *t;
    		    t=tsucc(root,num,null);
    		    printf("%d\n",t->val);
    		  }
    		if (kind==7)
    		  {
    	        treap_node *t;
    			t=kth(root,1); 
    		    printf("%d\n",t->val);
    	      }
    		if (kind==8)
    		  {
    		    treap_node *t;
    		    t=kth(root,k);
    		    printf("%d\n",t->val);
    		  }
    	  }
    }





    展开全文
  • 介绍树堆,在数据结构中也称Treap,是指有一个随机附加域满足堆的性质的二叉搜索树,其结构相当于以随机数据插入的二叉搜索树。其基本操作的期望时间复杂度为O(logn)。对于插入给节点随机分配一个优先级,先和二叉...

    介绍

    树堆,在数据结构中也称Treap,是指有一个随机附加域满足堆的性质的二叉搜索树,其结构相当于以随机数据插入的二叉搜索树。其基本操作的期望时间复杂度为O(log⁡2n)O(\log_2n)O(log2n)

    对于插入

    给节点随机分配一个优先级,先和二叉排序树的插入一样,先把要插入的点插入到一个叶子上,然后跟维护二叉平衡树一样,如果当前节点的优先级比父亲大就旋转,如果当前节点是父亲的左儿子就右旋,如果当前节点是父亲的右儿子就左旋。
    通常来说,优先级是伴随着访问次数来改变的。

    证明

    在这里我们先假设优先级的分布是稠密的。
    如果不是稠密的,可以通过映射来构造一个稠密的分布:
    把优先级从小到大排序,然后把优先级直接用序号代替。这样就得到了一个稠密的分布
    设我们要插入的节点的优先级为XXX,treap里面最大的优先级为LimitLimitLimit,简称LLL
    首先,如果X≥LX \ge LXL,那么就不用旋转。
    所以我们讨论X≤LX \le LXL 的情况

    我们可以得到树高
    H≈log⁡2LH \approx \log_{2}{L}Hlog2L
    而我们的XXX 的目标树高为
    Hx≈log⁡2XH_x \approx \log_{2}{X}Hxlog2X
    每次旋转,X都会减少一层树高(升上去了)
    所以我们的旋转次数
    Spin=H−Hx≈log⁡2L−log⁡2XSpin=H -H_x \approx \log_{2}{L} - \log_{2}{X}Spin=HHxlog2Llog2X
    由于我们的X是在[0,L][ 0,L][0,L] 内等可能的
    那么期望旋转次数为加权平均数
    ∑X=0L1L∗(log⁡2L−log⁡2X)\sum_{X=0}^L \frac{1}{L}*(\log_{2}{L} - \log_{2}{X})X=0LL1(log2Llog2X)

    ≈1L∫0L(log⁡2L−log⁡2X)dX\approx\frac{1}{L} \int_0^L(\log_{2}{L} - \log_{2}{X}) d{X}L10L(log2Llog2X)dX

    =1Lln⁡2[Xln⁡L−Xln⁡X+X]0L=\frac{1}{L \ln{2}} [X\ln{L} -X\ln{X} +X]_0^L=Lln21[XlnLXlnX+X]0L
    =1ln⁡2−0=1.44=\frac{1}{\ln{2}}-0=1.44=ln210=1.44
    证明完毕.

    展开全文
  • treap随想

    2018-08-22 18:06:13
    刚才YY了出了一种数据结构,也不知道叫什么名字(我的意思是,估计以前已经有很多人YY出来过并且已经命了名了),也不知道时间复杂度是否正确(毕竟这是YY出来的),如果各位大神发现了本文证明中的问题,欢迎在下方...
  • POJ 3481 treap

    2014-09-11 20:29:00
    相对于其他高级BST,treap树实现应该算最简单了,利用的是随机树产生的理论的二叉排序树时间复杂度为O(nlgn)来实现,具体证明 算法导论 中有。 推荐NOCOW中的讲解,关于二叉排序树相当完整! treap动画展示:...
  • Treap 的实现

    2013-03-17 21:05:23
    学会 BST 后,Treap 就比较好学了。 在 BST 的基础上,给每个节点加个...这样随机以后,树高的期望高度被证明为 log(n)。 从而使得操作的复杂度为 log(n) 。 /* Title : Treap Author: nyist_xiaod Date : 2013
  • 平衡树——Treap

    2017-03-10 21:01:50
    并且,优先级满足堆的性质(即父节点大于左右儿子),在插入一个值后,就随机送一个优先级,由于可以证明,在随机插入顺序下,树的深度期望是logn,所以,只要我们能够在每次操作后能够保证Treap的性质,那么它单次操作...
  • Treap(树堆)

    2016-02-19 14:37:00
    treap是排序二叉树的一种改进,因为排序二叉树有可能会造成链状结构的时候复杂度变成O(n^2)所以通过随机一个优先级的方法来维持每次让优先级最大的作为树根,然后形成一个满足: A. 节点中的key满足排序二叉树...
  • 排序二叉树和treap

    2013-11-09 21:39:00
    可以证明的是,在一颗排序二叉树中查找、插入和删除的算法复杂度都是树的高度,但是由于排序二叉树的建树和建树过程中选择的序列顺序有关,那么建树的好坏会直接影响其结构的效率,理论上数学期望为O(logn),最
  • 1.概述 平衡树,是一种高级数据结构,是基于二叉查找树的一种数据结构。 对二叉查找树不理解的读者这里有一个作者的简单总结: ...根据理论证明,二叉查找树在 随机数据 的情况下表现良好,平均时间复杂度是 O(nlog
  • 百折不饶,再交一次,更新复杂度证明 这里是HYF,蒟蒻一只,最近因某些原因开始学数据结构了,然后就写了这篇题解。 下面给大家介绍一个全新的数据结构,暂且称作IST(Immortal segment tree),你们也可以称作YYC ...
  • 替罪羊树

    2018-03-02 13:55:00
    终于去学了一下替罪羊。...虽然我没有看具体对复杂度证明。 1 #include<bits/stdc++.h> 2 using namespace std; 3 const int inf=1e5+10; 4 const double alpha=0.75; 5 int n,rt...
  • 线段树分裂 以某个键值为中点将线段树分裂成左右两部分,应该类似Treap...至于又有合并又有分裂的复杂度,蒟蒻一直不会比较有说服力的证明,直到看见SovietPower巨佬的题解 对于只有合并:合并两棵线段树的过程,是...
  • 关于splay的一些基本操作复杂度正确性证明和实现可以参考网上其他博客,这里就不在详细说明。 一些定义 先简单说明代码中的变量含义: f[a]表示splay的节点aaa的父亲节点 son[0/1][a]表示splay的节点aaa的左右儿子,...
  • codeforces706E

    2018-09-11 18:08:00
    好精妙的一道题啊 传送门:here 大致题意:有一个$ n*m$的矩阵,q次询问每次交换给定两个无交矩阵的对应元素,求操作后的...然后感觉复杂度一千万$ *log$甚至比暴力慢(事实证明确实如此) 正解其实又好写又快速,...

空空如也

空空如也

1 2
收藏数 22
精华内容 8
关键字:

treap复杂度证明