某岛

… : "…アッカリ~ン . .. . " .. .
April 6, 2020

Luogu 平衡树模板系列

普通平衡树

Luogu | BZOJ

namespace SBT {
    const static int N = int(1e5) + 9;
    int c[2][N], sz[N], ky[N], tot;
#define l c[d]
#define r c[!d]
#define lx l[x]
#define rx r[x]
#define kx ky[x]
#define sx sz[x]
#define d 0
    int new_node(int v = 0){
        int x=tot++;lx=rx=0;
        sx=1;kx=v;
        return x;
    }
    void upd(int x){
        sx=sz[lx]+1+sz[rx];
    }
#undef d
    void rot(int &x,int d){
        int y=rx;rx=l[y];l[y]=x;
        upd(x),upd(y),x=y;
    }
    void fix(int &x,int d){
        if (sz[l[lx]] > sz[rx]) rot(x,!d);
        else{
            if (sz[r[lx]] > sz[rx]) rot(lx,d),rot(x,!d);
            else return;
        }
        d=0,fix(lx,0),fix(rx,1);
        fix(x,0),fix(x,1);
    }
#define d 0
    void Ins(int &x,int v){
        if(!x) x = new_node(v);
        else{
            ++sz[x]; Ins(c[v>kx][x],v);
            fix(x,v>kx);
        }
    }
    int d_key; void Del(int &x,int v){
        --sx;if(kx==v||(v<kx&&!lx)||(v>kx&&!rx)){
            if(!lx||!rx) d_key = kx, x = lx | rx;
            else Del(lx,v+1), kx = d_key;
        }
        else Del(c[v>kx][x],v);
    }

    int Rank(int x,int v) {
        if (!x) return 0;
        return v <= kx ? Rank(lx, v) : sz[lx] + 1 + Rank(rx, v);
    }
    int Select(int x,int k) {
        if (k == sz[lx]) return kx;
        return k < sz[lx] ? Select(lx, k) : Select(rx, k-sz[lx]-1);
    }
    int upper(int x, int k) {
        int z;
        while (x) {
            if (kx > k) z = x, x = lx;
            else x = rx;
        }
        return ky[z];
    }
    int lower(int x,int k) {
        int z;
        while (x) {
            if (kx < k) z = x, x = rx;
            else x = lx;
        }
        return ky[z];
    }
#undef d
#undef sx
#undef kx
#undef lx
#undef rx
#undef l
#undef r
} using namespace SBT;

int rt;

int main(){

#ifndef ONLINE_JUDGE
    freopen("in.txt", "r", stdin);
    //freopen("out.txt", "w", stdout);
#endif

    tot = 1;
    int cmd, x;

    Rush {
        int cmd; RD(cmd); RDD(x);
        //cout << cmd << " " << x << endl;
        switch(cmd) {
            case 1:
                Ins(rt, x);
                break;
            case 2:
                Del(rt, x);
                break;
            case 3:
                OT(Rank(rt, x)+1);
                break;
            case 4:
                OT(Select(rt, x-1));
                break;
            case 5:
                OT(lower(rt, x));
                //OT(Select(rt, Rank(rt, x)-1));
                break;
            case 6:
                OT(upper(rt, x));
                //OT(Select(rt, Rank(rt, x+1)));
                break;
        }
    }
}
namespace Scapegoat_Tree {
    const static int N = int(1e5) + 9;
    const static DB alpha = 0.7;
    int c[2][N], sz[N], ky[N], tot;
#define l c[d]
#define r c[!d]
#define lx l[x]
#define rx r[x]
#define kx ky[x]
#define sx sz[x]
#define d 0
    int new_node(int v = 0){
        int x=tot++;lx=rx=0;
        sx=1;kx=v;
        return x;
    }
    void upd(int x){
        sx=sz[lx]+1+sz[rx];
    }
    bool bad(int x) {
        return max(sz[lx], sz[rx]) >= int(sx * alpha);
    }
    void build(int &x, int ll, int rr, VI& T) {
        if (ll >= rr) x = 0;
        else {
            int ml = (ll+rr) >> 1, mr = ml + 1;
            x = T[ml];
            build(lx, ll, ml, T);
            build(rx, mr, rr, T);
            upd(x);
        }
    }
    void collect(int x, VI& T) {
        if (!x) return;
        collect(lx, T); T.PB(x); collect(rx, T);
    }
    void rebuild(int& x) {
        VI T; collect(x, T);
        build(x, 0, SZ(T), T);
    }
    void Ins(int &x,int v){
        if(!x) x = new_node(v);
        else{
            ++sz[x]; Ins(c[v>kx][x],v);
            if (bad(x)) rebuild(x);
        }
    }
    int d_key; void Del(int &x,int v){
        --sx;if(kx==v||(v<kx&&!lx)||(v>kx&&!rx)){
            if(!lx||!rx) d_key = kx, x = lx | rx;
            else Del(lx,v+1), kx = d_key;
        }
        else Del(c[v>kx][x],v);
    }

    int Rank(int x,int v) {
        if (!x) return 0;
        return v <= kx ? Rank(lx, v) : sz[lx] + 1 + Rank(rx, v);
    }
    int Select(int x,int k) {
        if (k == sz[lx]) return kx;
        return k < sz[lx] ? Select(lx, k) : Select(rx, k-sz[lx]-1);
    }
    int upper(int x, int k) {
        int z;
        while (x) {
            if (kx > k) z = x, x = lx;
            else x = rx;
        }
        return ky[z];
    }
    int lower(int x,int k) {
        int z;
        while (x) {
            if (kx < k) z = x, x = rx;
            else x = lx;
        }
        return ky[z];
    }

    void inorder(int x) {
        if (!x) return;
        inorder(lx);
        printf("%d ", ky[x]);
        inorder(rx);
    }

#undef d
#undef sx
#undef kx
#undef lx
#undef rx
#undef l
#undef r
} using namespace Scapegoat_Tree;

int rt;

int main(){

#ifndef ONLINE_JUDGE
    freopen("in.txt", "r", stdin);
    //freopen("out.txt", "w", stdout);
#endif

    tot = 1;
    int cmd, x;

    Rush {
        int cmd; RD(cmd); RDD(x);
        //cout << cmd << " " << x << endl;
        switch(cmd) {
            case 1:
                Ins(rt, x);
                break;
            case 2:
                Del(rt, x);
                break;
            case 3:
                OT(Rank(rt, x)+1);
                break;
            case 4:
                OT(Select(rt, x-1));
                break;
            case 5:
                OT(lower(rt, x));
                //OT(Select(rt, Rank(rt, x)-1));
                break;
            case 6:
                OT(upper(rt, x));
                //OT(Select(rt, Rank(rt, x+1)));
                break;
        }
    }
}

文艺平衡树

Luogu

namespace Treap {
    const static int N = int(1e5) + 9;
    int c[2][N], sz[N], pr[N], rev[N], tot;
    LL ky[N], ss[N];
#define l c[d]
#define r c[!d]
#define lx l[x]
#define rx r[x]
#define kx ky[x]
#define sx sz[x]
#define d 0
    inline int new_node(LL v = 0) {
        int x=tot++;lx=rx=0;
        sx=1;kx=v;pr[x]=rand();ss[x]=v;rev[x]=0;
        return x;
    }
    inline int copy_node(int y) {
        int x = tot++;lx=l[y];rx=r[y];
        sx=sz[y];kx=ky[y];pr[x]=pr[y];ss[x]=ss[y];rev[x]=rev[y];
        return x;
    }
    inline void _rev(int x) {
      // if (!x) return;
        rev[x] ^= 1;
    }
    inline void upd(int x) {
        sx=sz[lx]+1+sz[rx];
        ss[x]=ss[lx]+kx+ss[rx];
    }
    inline void rls(int x) {
        if (!rev[x]) return;
        _rev(lx);
        _rev(rx);
        swap(lx, rx);
        rev[x] = 0;
    }


    void split(int x, int p, int &a, int &b){
        if (!x) {
            a = b = 0;
            return;
        }
        rls(x);
        if(p <= sz[lx]) split(lx, p, a, lx), b = x;
        else split(rx, p-sz[lx]-1, rx, b), a = x;
        upd(x);
    }

    int merge(int a, int b){
        if(!a||!b) return a|b;
        rls(a); rls(b);
        if (pr[a] > pr[b]){
            r[a] = merge(r[a], b); upd(a);
            return a;
        }
        else{
            l[b] = merge(a, l[b]); upd(b);
            return b;
        }
    }

    int Select(int x,int ll,int rr) {
        int a, b, _;
        split(x, rr, a, _);
        split(a, ll-1, _, b);
        return b;
    }


    void Inorder(int x) {
        if (!x) return;
        rls(x);
        Inorder(lx);
        printf("%lld ", ky[x]);
        Inorder(rx);
    }

    void Build(int &x, int ll, int rr) {
        if (ll < rr) {
            int ml = (ll + rr) >> 1;
            int mr = ml + 1;
            x = new_node(ml);
            Build(lx, ll, ml);
            Build(rx, mr, rr);
            upd(x);
        }
    }

#undef d
#undef sx
#undef kx
#undef lx
#undef rx
#undef l
#undef r
} using namespace Treap;

int root;

int main(){

#ifndef ONLINE_JUDGE
    //freopen("in.txt", "r", stdin);
    //freopen("out.txt", "w", stdout);
#endif

    tot = 1;

    int n; RD(n); Build(root, 1, n+1);

    Rush {
        int l, r, a, b, c; RD(l, r);
        split(root, r, a, c);
        split(a, l-1, a, b);
        _rev(b);
        root = merge(merge(a, b), c);
    }

    Inorder(root);
}

https://www.luogu.com.cn/record/32534504

可持久化平衡树

Luogu

数据不太给力,替罪羊还没有朴素跑得快。。


namespace Scapegoat_Tree {
    const static int N = int(5e7) + 9;
    const static DB alpha = 0.7;
    int c[2][N], sz[N], ky[N], tot;
#define l c[d]
#define r c[!d]
#define lx l[x]
#define rx r[x]
#define kx ky[x]
#define sx sz[x]
#define d 0
    
    int new_node(int v = 0){
        int x=tot++;lx=rx=0;
        sx=1;kx=v;
        return x;
    }
    int copy_node(int y) {
        int x = tot++;lx=l[y];rx=r[y];
        sx=sz[y];kx=ky[y];
        return x;
    }
    void upd(int x){
        sx=sz[lx]+1+sz[rx];
    }
    bool bad(int x) {
        return 0;
        return max(sz[lx], sz[rx]) >= int(sx * alpha);
    }
    void build(int &x, int ll, int rr, VI& T) {
        if (ll >= rr) x = 0;
        else {
            int ml = (ll+rr) >> 1, mr = ml + 1;
            x = T[ml];
            build(lx, ll, ml, T);
            build(rx, mr, rr, T);
            upd(x);
        }
    }
    void collect(int x, VI& T) {
        if (!x) return;
        collect(lx, T); T.PB(x); collect(rx, T);
    }
    void rebuild(int& x) {
        VI T; collect(x, T);
        build(x, 0, SZ(T), T);
    }
    void Ins(int &x,int v){
        if(!x) x = new_node(v);
        else{
            x = copy_node(x);
            ++sx; Ins(c[v>kx][x],v); //upd(x);
            if (bad(x)) rebuild(x);
        }
    }
    int d_key; void Del(int &x,int v){
        x = copy_node(x);
        --sx;if(kx==v||(v<kx&&!lx)||(v>kx&&!rx)){
            if(!lx||!rx) d_key = kx, x = lx | rx;
            else Del(lx,v+1), kx = d_key;
        }
        else Del(c[v>kx][x],v);
    }
    
    int Rank(int x,int v) {
        if (!x) return 0;
        return v <= kx ? Rank(lx, v) : sz[lx] + 1 + Rank(rx, v);
    }
    int Select(int x,int k) {
        if (k == sz[lx]) return kx;
        return k < sz[lx] ? Select(lx, k) : Select(rx, k-sz[lx]-1);
    }
    int upper(int x, int k) {
        int z;
        while (x) {
            if (kx > k) z = x, x = lx;
            else x = rx;
        }
        return ky[z];
    }
    int lower(int x,int k) {
        int z;
        while (x) {
            if (kx < k) z = x, x = rx;
            else x = lx;
        }
        return ky[z];
    }
    
    void inorder(int x) {
        if (!x) return;
        inorder(lx);
        printf("%d ", ky[x]);
        inorder(rx);
    }
    
#undef d
#undef sx
#undef kx
#undef lx
#undef rx
#undef l
#undef r
} using namespace Scapegoat_Tree;

int rt[N];

int main(){
    
#ifndef ONLINE_JUDGE
    freopen("in.txt", "r", stdin);
    //freopen("out.txt", "w", stdout);
#endif
    
    tot = 1;
    Ins(rt[0], 0x7fffffff);
    Ins(rt[0], int(0x80000001));
    
    //cout << 0x7fffffff << " " << int(0x80000001) << endl;
    
    int n; RD(n); REP_1(i, n) {
        int &r = rt[i];
        int t, cmd, x; RD(t, cmd); RDD(x); r = rt[t];
        switch(cmd) {
            case 1:
                Ins(r, x);
                break;
            case 2:
                if (Select(r, Rank(r, x)) == x) Del(r, x);
                break;
            case 3:
                OT(Rank(r, x));
                break;
            case 4:
                OT(Select(r, x));
                break;
            case 5:
                OT(lower(r, x));
                //OT(Select(r, Rank(r, x)-1));
                break;
            case 6:
                OT(upper(r, x));
                //OT(Select(r, Rank(r, x+1)));
                break;
        }
        //cout << " S"; inorder(r); cout << endl;
    }
}

https://www.luogu.com.cn/record/32520408

可持久化文艺平衡树

Luogu

namespace Treap {
    const static int N = int(5e7) + 9;
    int c[2][N], sz[N], pr[N], rev[N], tot;
    LL ky[N], ss[N];
#define l c[d]
#define r c[!d]
#define lx l[x]
#define rx r[x]
#define kx ky[x]
#define sx sz[x]
#define d 0
    inline int new_node(LL v = 0) {
        int x=tot++;lx=rx=0;
        sx=1;kx=v;pr[x]=rand();ss[x]=v;rev[x]=0;
        return x;
    }
    inline int copy_node(int y) {
        int x = tot++;lx=l[y];rx=r[y];
        sx=sz[y];kx=ky[y];pr[x]=pr[y];ss[x]=ss[y];rev[x]=rev[y];
        return x;
    }
    inline void _rev(int x) {
      // if (!x) return;
        rev[x] ^= 1;
    }
    inline void upd(int x) {
        sx=sz[lx]+1+sz[rx];
        ss[x]=ss[lx]+kx+ss[rx];
    }
    inline void rls(int x) {
        if (!rev[x]) return;
        if (lx) _rev(lx = copy_node(lx));
        if (rx) _rev(rx = copy_node(rx));
        swap(lx, rx);
        rev[x] = 0;
    }
    

    void split(int x, int p, int &a, int &b){
        if (!x) {
            a = b = 0;
            return;
        }
        rls(x); x = copy_node(x);
        if(p <= sz[lx]) split(lx, p, a, lx), b = x;
        else split(rx, p-sz[lx]-1, rx, b), a = x;
        upd(x);
    }
    
    int merge(int a, int b){
        if(!a||!b) return a|b;
        rls(a); rls(b);
        if (pr[a] > pr[b]){
            r[a] = merge(r[a], b); upd(a);
            return a;
        }
        else{
            l[b] = merge(a, l[b]); upd(b);
            return b;
        }
    }
    
    int Select(int x,int ll,int rr) {
        int a, b, _;
        split(x, rr, a, _);
        split(a, ll-1, _, b);
        return b;
    }
    
    
    void inorder(int x) {
        if (!x) return;
        rls(x);
        inorder(lx);
        printf("%lld ", ky[x]);
        inorder(rx);
    }
    
#undef d
#undef sx
#undef kx
#undef lx
#undef rx
#undef l
#undef r
} using namespace Treap;

int rt[N];

int main(){
    
#ifndef ONLINE_JUDGE
    //freopen("in.txt", "r", stdin);
    //freopen("out.txt", "w", stdout);
#endif
    
    tot = 1;
    
    int n; RD(n); REP_1(i, n) {
        int &root = rt[i];
        int t, cmd, a, b, c, _; RD(t, cmd); root = rt[t];
        LL p, l, r, x;
        
        switch(cmd) {
            case 1:
                RDD(p, x); p ^= last_ans; x ^= last_ans;
                split(root, p, a, b);
                root = merge(merge(a, new_node(x)), b);
                break;
            case 2:
                RDD(p); p ^= last_ans;
                split(root, p, a, b), split(a, p-1, a, _);
                root = merge(a, b);
                break;
            case 3:
                RDD(l, r); l ^= last_ans; r ^= last_ans;
                split(root, r, a, c);
                split(a, l-1, a, b);
                _rev(b);
                root = merge(merge(a, b), c);
                break;
            case 4:
                RDD(l, r); l ^= last_ans; r ^= last_ans;
                split(root, r, a, c);
                split(a, l-1, a, b);
                OT(ss[b]);
                break;
        }
    }
}

https://www.luogu.com.cn/record/32531112