無回転Treap狂から不回転へ

バランスツリーの部分を勉強しているとき、隣のC姓dalaoはTreapに夢中になっていたが、私はSplayの優美さに夢中になった.これはTreapに対する無関心を招いた.
これは何の役に立つのか,そんなに多くの操作をしても磁器にはならない,low
今はにぎやかで、バランスのとれた木を使う問題にぶつかるたびに、悔恨の涙(汗)がこぼれてきた.
Splayは本当に難しいですね.
だから、今日は、無回転Treapについてお話ししましょう.
スピンフリーTreap
スピンフリーTreapの最大の利点は、符号化が簡単で、サポートされている操作が多く、それに対応して、Splayより少し遅いことです.
無回転Treapの主な操作は2つあり、splitとmergeで、or o rを分裂して2本のTreapを合併することができる.この2つの操作により、多くの他の操作を拡張できます.
ぶんれつ
Treapのsplitは、あるTreapにおいてnum n u mの大きさの左のサブツリーを分裂させることを支持し、あるいはkよりも重み値の小さいサブツリーを分裂させることを支持する.Treapは二叉探索ツリーの性質を有するため、size or o r keyによって再帰的に分裂すればよい
同時にオブジェクトメンテナンスにより分裂後の2つのtreapのそれぞれの位置関係はsizeで分裂する

void split(int now,int num,int &x,int &y) {
    if(!now) x=y=0;
    else {
        pushdown(now);
        if(num<=siz[L]) {y=now;split(L,num,x,L);}
        else {x=now;split(R,num-siz[L]-1,R,y);}
        update(now);
    }
}

keyで分裂

void split(int now,int k,int &x,int &y) {
    if(!now) x=y=0;
    else {
        //  k     ,    key     
        if(kelse {x=now;split(R,k,R,y);}
        update(now);
    }
}

結合
Treapのマージ操作は、2本のTreapを一定の順序で組み合わせ、その最終形態は2つの側面によって決定される: とpos(私は通常それを自己平衡権と呼ぶ)明らかに、Treapの原理に基づいて、通常posはより小さな位置に置かれ、同時にtreapは二叉探索木でもある.その相対位置が両者の親子関係(左サブツリーor o r右サブツリーに属する)を決定する左バイアスツリーと同様に再帰的にマージすればよい

int merge(int a,int b) {
    if(a*b==0) return a+b;
    if(pos[a]1]=merge(ch[a][1],b);
        update(a);
        return a;
    }
    else {
        ch[b][0]=merge(a,ch[b][0]);
        update(b);
        return b;
    }
}

挿入splitとmergeによって、insertを簡単に実現することができます.
位置による挿入
まず挿入する位置の左側の部分を分割し、次に左側の部分を順番に結合し、ノード、右側の部分を挿入します.
ウェイト値による挿入
同様に,v vより小さいノードを左サブツリーに置き,順次マージする.

void insert(int v) {
    int a,b;
    split(rt,v,a,b);
    rt=merge(merge(a,make_node(v)),b);
}

削除splitとmergeによって、delを簡単に実現することができます.
場所による削除
削除位置を抽出し、左右のノードをマージ
権限値による削除
k以下のノードを抽出する、k-1以下の部分を抽出すると、k kに等しい値がどれだけあるかにより、kに等しいサブツリーを左右のサブノードに直接結合することで、1つのノードのみを削除することが保証される.すべて削除するには、左右の部分を直接マージします.

void del(int v) {
    int a,b,c;
    split(rt,v,a,b);
    split(a,v-1,a,c);
    c=merge(ch[c][0],ch[c][1]);
    rt=merge(merge(a,c),b);
}

くかんそうさsplayと同様に、splitを使用して区間を抽出し、マークを付け、最後にmerge例えば、区間反転

void rev(int l,int r) {
    split(rt,r+1,a,b);
    split(a,l,c,d);
    rev[d]^=1;
    swap(ch[d][0],ch[d][1]);
}

じっこう
BZOJ 3223文芸バランスツリー

#include 
using namespace std;
#define L ch[now][0]
#define R ch[now][1]
#define mid ((l+r)>>1)
typedef pair <int,int> p;
const int N = 100010;
int n,m,rt;
struct treap {
    int pos[N],ch[N][2],siz[N],rev[N],rt,key[N];
    void update(int now) {siz[now]=siz[L]+siz[R]+1;}
    void Rev(int now) {swap(L,R);}
    void pushdown(int now) {if(rev[now]) {rev[now]^=1;rev[L]^=1;rev[R]^=1;Rev(L);Rev(R);}}
    int merge(int a,int b) {
        if(a*b==0) return a?a:b;
        pushdown(a);pushdown(b);
        if(pos[a]1]=merge(ch[a][1],b);
            update(a);
            return a;
        }
        else {
            ch[b][0]=merge(a,ch[b][0]);
            update(b);
            return b;
        }
    }
    void split(int now,int num,int &x,int &y) {
        if(!now) x=y=0;
        else {
            pushdown(now);
            if(num<=siz[L]) {y=now;split(L,num,x,L);}
            else {x=now;split(R,num-siz[L]-1,R,y);}
            update(now);
        }
    }
    int build(int l,int r) {
        if(l==r) {pos[l]=rand();siz[l]=1;key[l]=l-1;return l;}
        return merge(build(l,mid),build(mid+1,r));
    }
    void print(int now) {
        pushdown(now);
        if(L) print(L);
        if(key[now]>=1 && key[now]<=n) printf("%d ",key[now]);
        if(R) print(R);
    }
}t;
int read() {
    int _ans=0,_flag=1;
    char _ch=getchar();
    while((_ch != '-') && (_ch > '9' || _ch < '0')) _ch=getchar();
    if(_ch == '-') {_flag = -1;_ch = getchar();}
    while(_ch >= '0' && _ch <= '9') {_ans=_ans*10+_ch-'0';_ch=getchar();}
    return _ans*_flag;
}
int main() {
    n=read();m=read();
    rt=t.build(1,n+2);
    for(int i=1;i<=m;++i) {
        int l=read(),r=read(),a,b,c,d;
        t.split(rt,r+1,a,b);
        t.split(a,l,c,d);
        t.rev[d]^=1;
        t.Rev(d);
        rt=t.merge(c,t.merge(d,b));
    }
    t.print(rt);
    return 0;
}

LG-2464[SDOI 2008]うっとうしいJちゃん

#include 
using namespace std;
#define L ch[now][0]
#define R ch[now][1]
const int N = 400010;
map <int,int> p;
struct Treap {
    int key[N],pos[N],cnt,ch[N][2],rt[N],siz[N];
    int newnode(int k) {pos[++cnt]=rand();siz[cnt]=1;key[cnt]=k;return cnt;}
    void update(int now) {siz[now]=1+siz[L]+siz[R];}
    void split(int now,int k,int &x,int &y) {
        if(!now) {x=y=0;return;}
        if(kelse {x=now;split(R,k,R,y);}
        update(now);
    }
    int merge(int a,int b) {
        if(a*b==0) return a+b;
        if(pos[a]1]=merge(ch[a][1],b);
            update(a);
            return a;
        }
        else {
            ch[b][0]=merge(a,ch[b][0]);
            update(b);
            return b;
        }
    }
    void insert(int k,int v) {
        int a,b;
        split(rt[k],v,a,b);
        rt[k]=merge(a,merge(newnode(v),b));
    }
    void del(int k,int v) {
        int a,b,c;
        split(rt[k],v,a,b);
        split(a,v-1,a,c);
        c=merge(ch[c][0],ch[c][1]);
        rt[k]=merge(merge(a,c),b);
    }
    void query(int k,int l,int r) {
        int a,b,c;
        split(rt[k],r,a,b);
        split(a,l-1,a,c);
        printf("%d
",siz[c]);
        rt[k]=merge(merge(a,c),b);
    }
}t;
int n,m,cnt,a[N];
int read();
int main() {
    srand(time(NULL));
    n=read();m=read();
    for(int i=1;i<=n;++i) {
        a[i]=read();
        if(p[a[i]]==0) p[a[i]]=++cnt;
        a[i]=p[a[i]];
        t.insert(a[i],i);
    }
    for(int i=1;i<=m;++i) {
        char ch=getchar();
        while(ch!='Q' && ch!='C') ch=getchar();
        if(ch=='Q') {
            int l=read(),r=read(),k=read();
            k=p[k];
            t.query(k,l,r);
        }
        else {
            int pos=read(),k=read();
            t.del(a[pos],pos);
            if(p[k]==0) p[k]=++cnt;
            a[pos]=p[k];
            t.insert(a[pos],pos);
        }
    }
    return 0;
}
int read() {
    int _ans=0,_flag=1;
    char _ch=getchar();
    while((_ch != '-') && (_ch > '9' || _ch < '0')) _ch=getchar();
    if(_ch == '-') {_flag = -1;_ch = getchar();}
    while(_ch >= '0' && _ch <= '9') {_ans=_ans*10+_ch-'0';_ch=getchar();}
    return _ans*_flag;
}