Treap 模板

感觉平衡树也没有以前想的那么玄乎，（其实set超好用的），非旋式Treap挺好理解，和可并堆，二叉搜索树有很大联系

推荐博客：http://memphis.is-programmer.com/posts/46317.html

模板也是摘自这位dalao的

#include<bits/stdc++.h>

using namespace std;

#define maxn 2000005

#define rep(i,x,y) for(int i=x;i<=y;++i)

#define dep(i,x,y) for(int i=x;i>=y;--i)

struct Treap{

    Treap *l,*r;

    int fix,key,size;

    Treap(int key_):fix(rand()),key(key_),l(NULL),r(NULL),size(){}

    inline void updata(){

        size=+(l?l->size:)+(r?r->size:);

    }

}*root;

typedef pair<Treap*,Treap*> Droot;//用来Split返回两个根 

inline int Size(Treap *x){return x?x->size:;}//这样求size可以防止访问空指针 

Treap *Merge(Treap *A,Treap *B){//合并操作

    if(!A)return B;

    if(!B)return A;

    if(A->fix<B->fix){

        A->r=Merge(A->r,B);

        A->updata();

        return A;

    }

    else{

        B->l=Merge(A,B->l);

        B->updata();

        return B;

    }

}

Droot Split(Treap *x,int k){//拆分操作

    if(!x)return Droot(NULL,NULL);

    Droot y;

    if(Size(x->l)>=k){

        y=Split(x->l,k);

        x->l=y.second;

        x->updata();

        y.second=x;

    }

    else{

        y=Split(x->r,k-Size(x->l)-);

        x->r=y.first;

        x->updata();

        y.first=x;

    }

    return y;

}

Treap *Build(int *a){//建造操作

    static Treap *stack[maxn],*x,*last;

    int p=;

    rep(i,,a[]){

        x=new Treap(a[i]);

        last=NULL;

        while(p && stack[p]->fix>x->fix){

            stack[p]->updata();

            last=stack[p];

            stack[p--]=NULL;

        }

        if(p) stack[p]->r=x;

        x->l=last;

        stack[++p]=x;

    }

    while(p) stack[p--]->updata();

    return stack[];

}

int Findkth(int k){//查找第K小

    Droot x=Split(root,k-);

    Droot y=Split(x.second,);

    Treap *ans=y.first;

    root=Merge(Merge(x.first,ans),y.second);

    return ans->key;

}

int Getkth(Treap *x,int v){//询问一个数是第几大

    if(!x)return ;

    return v<x->key?Getkth(x->l,v):Getkth(x->r,v)+Size(x->l)+;

}

void Insert(int v){//插入操作

    int k=Getkth(root,v);

    Droot x=Split(root,k);

    Treap *n=new Treap(v);

    root=Merge(Merge(x.first,n),x.second);

}

void Delete(int k){//删除操作

    Droot x=Split(root,k-);

    Droot y=Split(x.second,);

    root=Merge(x.first,y.second);

}

int a[maxn],M,x,y;

int main(){

    scanf("%d",a);

    rep(i,,a[]) scanf("%d",a+i);

    sort(a+,a++a[]);

    root=Build(a);

    scanf("%d",&M);

    while(M--){

        char ch=getchar();

        while(ch!='Q' && ch!='A' && ch!='D') ch=getchar();

        scanf("%d",&x);

        if(ch=='Q') printf("%d\n",Findkth(x));

        if(ch=='A') Insert(x);

        if(ch=='D') Delete(x);

    }

}

改了一下之后就A了文艺平衡树

#include<bits/stdc++.h>

using namespace std;

#define maxn 2000005

#define rep(i,x,y) for(int i=x;i<=y;++i)

#define dep(i,x,y) for(int i=x;i>=y;--i)

int n;

struct Treap{

    Treap *l,*r;

    int fix,key,size;

    bool fg;

    Treap(int key_):fix(rand()),key(key_),l(NULL),r(NULL),size(){}

    inline void updata(){

        size=+(l?l->size:)+(r?r->size:);

    }

}*root;

typedef pair<Treap*,Treap*> Droot;//用来Split返回两个根 

inline int Size(Treap *x){return x?x->size:;}//这样求size可以防止访问空指针

void pushdown(Treap *x){

    if(!x->fg)return;

    x->fg=;

    swap(x->l,x->r);

    if( x->l ) x->l->fg^=;

    if( x->r ) x->r->fg^=;

}

Treap *Merge(Treap *A,Treap *B){//合并操作

    if(!A)return B;

    if(!B)return A;

    pushdown(A);pushdown(B);

    if(A->fix<B->fix){

        A->r=Merge(A->r,B);

        A->updata();

        return A;

    }

    else{

        B->l=Merge(A,B->l);

        B->updata();

        return B;

    }

}

Droot Split(Treap *x,int k){//拆分操作

    if(!x)return Droot(NULL,NULL);

    Droot y;

    pushdown(x);

    if(Size(x->l)>=k){

        y=Split(x->l,k);

        x->l=y.second;

        x->updata();

        y.second=x;

    }

    else{

        y=Split(x->r,k-Size(x->l)-);

        x->r=y.first;

        x->updata();

        y.first=x;

    }

    return y;

}

Treap *build(int L,int R){

    if(L>R)return NULL;

    int mid=(L+R)>>,key=mid-;

    Treap *x =new Treap(key);

    x->l = build(L,mid-);

    x->r = build(mid+,R);

    x->updata();

    return x;

}

Treap *Build(int *a){//建造操作

    static Treap *stack[maxn],*x,*last;

    int p=;

    rep(i,,a[]){

        x=new Treap(a[i]);

        last=NULL;

        while(p && stack[p]->fix>x->fix){

            stack[p]->updata();

            last=stack[p];

            stack[p--]=NULL;

        }

        if(p) stack[p]->r=x;

        x->l=last;

        stack[++p]=x;

    }

    while(p) stack[p--]->updata();

    return stack[];

}

void order(Treap *x){

    if( x == NULL ) return;

    pushdown(x);

    order(x->l);

    if(x->key >=  && x->key<=n)printf("%d ",x->key);

    order(x->r);

}

void rev(int L,int R){

    Droot tmp1=Split(root,R+);

    Droot tmp2=Split(tmp1.first,L);

    tmp2.second->fg^=;

    root = NULL;

    root = Merge(tmp2.first,tmp2.second);

    root = Merge(root,tmp1.second);

}

//int Findkth(int k){//查找第K小

//    Droot x=Split(root,k-1);

//    Droot y=Split(x.second,1);

//    Treap *ans=y.first;

//    root=Merge(Merge(x.first,ans),y.second);

//    return ans->key;

//}

//int Getkth(Treap *x,int v){//询问一个数是第几大

//    if(!x)return 0;

//    return v<x->key?Getkth(x->l,v):Getkth(x->r,v)+Size(x->l)+1;

//}

//void Insert(int v){//插入操作

//    int k=Getkth(root,v);

//    Droot x=Split(root,k);

//    Treap *n=new Treap(v);

//    root=Merge(Merge(x.first,n),x.second);

//}

//void Delete(int k){//删除操作

//    Droot x=Split(root,k-1);

//    Droot y=Split(x.second,1);

//    root=Merge(x.first,y.second);

//}

//int a[maxn],M,x,y;

int M;

int main(){

    //scanf("%d",a);

    //rep(i,1,a[0]) scanf("%d",a+i);

    //sort(a+1,a+1+a[0]);

    //root=Build(a);

    scanf("%d",&n);

    scanf("%d",&M);

    root=build(,n+);

    int L,R;

    while(M--){

//        char ch=getchar();

//        while(ch!='Q' && ch!='A' && ch!='D') ch=getchar();

//        scanf("%d",&x);

//        if(ch=='Q') printf("%d\n",Findkth(x));

//        if(ch=='A') Insert(x);

//        if(ch=='D') Delete(x);

        scanf("%d%d",&L,&R);

        rev(L,R);

    }

    order(root);

}

再粘一个非指针版的我敬爱的学长szb写的，浙大一本爷

#include <iostream>

#include <cstdio>

#include <cstdlib>

using namespace std;

#define mp make_pair

typedef pair<int,int> par;

const int N=;

const int inf=1e9;

int n,root,cnt;

int l[N],r[N],key[N],rnd[N],size[N];

int readin() {

    int x=,f=; char ch=getchar();

    while(ch>''||ch<'') {if(ch=='-')f=-;ch=getchar();}

    while(ch>=''&&ch<='') {x=x*+ch-'';ch=getchar();}

    return x*f;

}

void update(int x) {

    size[x]=size[l[x]]+size[r[x]]+;

    return;

}

int merge(int x,int y) {

    if (!x||!y)

        return x+y;

    if (rnd[x]<rnd[y]) {

        r[x]=merge(r[x],y);

        update(x); return x;

    }

    else {

        l[y]=merge(x,l[y]);

        update(y); return y;

    }

}

par split(int x,int k) {

    if (k==)

        return mp(,x);

    int ls=l[x],rs=r[x];

    if (k<=size[l[x]]) {

        par t=split(l[x],k);

        l[x]=t.second; update(x);

        return mp(t.first,x);

    }

    else if (k==size[l[x]]+) {

        r[x]=; update(x);

        return mp(x,rs);

    }

    else {

        par t=split(rs,k-(size[l[x]]+));

        r[x]=t.first; update(x);

        return mp(x,t.second);

    }

}

int query_rank(int x,int k) {

    int ans=,t=inf;

    while(x) {

        if (k==key[x]) t=min(t,ans+size[l[x]]+);

        if (k>key[x]) ans+=(size[l[x]]+),x=r[x];

        else x=l[x];

    }

    return t==inf?ans:t;

}

void insert(int x) {

    int k=query_rank(root,x);

    par t=split(root,k);

    key[++cnt]=x,rnd[cnt]=rand(),size[cnt]=;

    root=merge(t.first,cnt);

    root=merge(root,t.second);

    return;

}

void del(int x) {

    int k=query_rank(root,x);

    par t1=split(root,k);

    par t2=split(t1.first,k-);

    root=merge(t2.first,t1.second);

    return;

}

int query_num(int x,int k) {

    while() {

        if (k==size[l[x]]+) return key[x];

        if (k<=size[l[x]]) x=l[x];

        else k-=(size[l[x]]+),x=r[x];

    }

}

int query_pre(int x,int k) {

    int ans=-inf;

    while(x) {

        if (key[x]<k)

            ans=max(ans,key[x]),x=r[x];

        else

            x=l[x];

    }

    return ans;

}

int query_sub(int x,int k) {

    int ans=inf;

    while(x) {

        if (key[x]>k)

            ans=min(ans,key[x]),x=l[x];

        else

            x=r[x];

    }

    return ans;

}

int main() {

    int opt,x;

    n=readin();

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

        opt=readin(),x=readin();

        if (opt==) insert(x);

        else if (opt==) del(x);

        else if (opt==) printf("%d\n",query_rank(root,x));

        else if (opt==) printf("%d\n",query_num(root,x));

        else if (opt==) printf("%d\n",query_pre(root,x));

        else printf("%d\n",query_sub(root,x));

    }

    return ;

}

序列终结者，调了好久发现区间截取错了那我咋A的文艺平衡树啊？？？啊~好像是那个程序建树的时候整个往后串了一位

#include<bits/stdc++.h>

using namespace std;

#define maxn 2000005

int n;

#define inf 1000000000

struct Treap{

    Treap *l,*r;

    int fix,key,size,mx,add;

    bool fg;

    Treap(int key_):fix(rand()),key(key_),l(NULL),r(NULL),size(),mx(),fg(),add(){}

    void addv(int w){mx+=w;add+=w;key+=w;}

    inline void updata(){

        size=+(l?l->size:)+(r?r->size:);

        mx=max(key,max((l?l->mx:-inf),(r?r->mx:-inf)));

    }

}*root;

typedef pair<Treap*,Treap*> Droot;//用来Split返回两个根 

inline int Size(Treap *x){return x?x->size:;}//这样求size可以防止访问空指针

void pushdown(Treap *x){

    if(x->fg){

    x->fg=;

    swap(x->l,x->r);

    if( x->l ) x->l->fg^=;

    if( x->r ) x->r->fg^=;}

    if(x->add){

        if( x->l ) x->l->addv(x->add);

        if( x->r ) x->r->addv(x->add);

        x->add=;

    }

}

Treap *Merge(Treap *A,Treap *B){//合并操作

    if(!A)return B;

    if(!B)return A;

    pushdown(A);pushdown(B);

    if(A->fix<B->fix){

        A->r=Merge(A->r,B);

        A->updata();

        return A;

    }

    else{

        B->l=Merge(A,B->l);

        B->updata();

        return B;

    }

}

Droot Split(Treap *x,int k){//拆分操作

    if(!x)return Droot(NULL,NULL);

    Droot y;

    pushdown(x);

    if(Size(x->l)>=k){

        y=Split(x->l,k);

        x->l=y.second;

        x->updata();

        y.second=x;

    }

    else{

        y=Split(x->r,k-Size(x->l)-);

        x->r=y.first;

        x->updata();

        y.first=x;

    }

    return y;

}

void rev(int L,int R){

    Droot tmp1=Split(root,R);

    Droot tmp2=Split(tmp1.first,L-);

    tmp2.second->fg^=;

    root = Merge( Merge(tmp2.first,tmp2.second),tmp1.second);

}

void up(int L,int R,int v){

    Droot tmp1=Split(root,R);

    Droot tmp2=Split(tmp1.first,L-);

    tmp2.second->addv(v);

    root = Merge(Merge(tmp2.first,tmp2.second),tmp1.second);

}

int query(int L,int R){

    Droot tmp1=Split(root,R);

    Droot tmp2=Split(tmp1.first,L-);

    int ret=tmp2.second->mx;

    root = Merge(Merge(tmp2.first,tmp2.second),tmp1.second);

    return ret;

}

int M;

int main(){

    scanf("%d",&n);

    scanf("%d",&M);

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

        Treap *a=new Treap();

        root=Merge(root,a);

    }

    int L,R;

    int f,v;

    while(M--){

        scanf("%d",&f);

        if(f==){

        scanf("%d%d%d",&L,&R,&v);

        up(L,R,v);}

        else if(f==){

            scanf("%d%d",&L,&R); rev(L,R);

        }

        else {

            scanf("%d%d",&L,&R);

            printf("%d\n",query(L,R));

        }

    }

}

巴特西

Treap 模板

最新文章

热门文章