• https://www.luogu.com.cn/problem/P3369

#include <lastweapon/io>
using namespace lastweapon;

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); RD(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;
        }
    }
}

#include <lastweapon/io>
using namespace lastweapon;

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); RD(x);
        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;
        }
    }
}

Posted by xiaodao
Category: 日常