一种有趣的暴力重构思想 SBT。

学习链接

https://zhuanlan.zhihu.com/p/21263304

例题链接

https://www.luogu.org/problemnew/show/P3369

主要思想

若子树不平衡，则 $O(n)$ 暴力重构。
均摊复杂度 $O(n\log n)$，期望复杂度较为优秀。

在指针的实现上有一些细节（比如用到了指针指指针等），所以说只是应用思想的话可能考场上会 WA 飞
所以还是搞了个模板...

UPD: 2018-11-9

更新了模板，修正了几个错误。

• 替罪羊树不能使用普通的递归前驱后继（会导致复杂度不正确），需要用 Rank 和 kth 来代替。
• 删除的结点个数如果超过树的结点个数的一半则直接暴力重构。

Code

// Code by ajcxsu
// Problem: baltree

#include<bits/stdc++.h>
using namespace std;

template<typename T> inline void gn(T &x) {
    char ch=getchar(), pl=0; x=0;
    while(ch<'0' || ch>'9') pl=(ch=='-'), ch=getchar();
    while(ch>='0' && ch<='9') x=x*10+ch-'0', ch=getchar(); x*=pl?-1:1;
}

const int N=1e5+10;
const double alpha=0.75;
struct Node *nil;
struct Node {
    Node *ch[2];
    int val, s, c;
    Node(int val=-0x3f3f3f3f):val(val) { s=c=1; ch[0]=ch[1]=nil; }
    int cmp(int x) { return x==val?-1:x>val; }
    void upd() { s=c+ch[0]->s+ch[1]->s; }
    bool bad() { return ch[0]->s>s*alpha+3 || ch[1]->s>s*alpha+3; }
} *rt, **bad;
int deled, tot;
void ini() { nil=new Node(), nil->ch[0]=nil->ch[1]=nil, nil->s=nil->c=0; bad=&nil, rt=nil; }

Node *stk[N]; int t;
void re1(Node *x) {
    if(x==nil) return;
    re1(x->ch[0]);
    if(x->c) stk[++t]=x;
    re1(x->ch[1]);
    if(!x->c) delete x;
}
Node *re2(int l, int r) {
    if(l==r) { stk[l]->ch[0]=stk[l]->ch[1]=nil; stk[l]->upd(); return stk[l]; }
    else if(l>r) return nil;
    int mid=(l+r)>>1;
    stk[mid]->ch[0]=re2(l, mid-1), stk[mid]->ch[1]=re2(mid+1, r);
    stk[mid]->upd(); return stk[mid];
}
void rebuild() {
    if(deled*2>tot) bad=&rt, tot-=deled, deled=0;
    if(bad!=&nil) re1(*bad), *bad=re2(1, t), bad=&nil, t=0;
}

void ins(Node *&x, int val) {
    if(x==nil) x=new Node(val);
    else {
        if(x->val==val) x->c++;
        else ins(x->ch[x->cmp(val)], val);
    }
    if(x->bad()) bad=&x;
    x->upd();
}
void del(Node *&x, int val) {
    int d=x->cmp(val);
    if(d==-1) x->c--;
    else del(x->ch[d], val);
    if(x->bad()) bad=&x;
    x->upd();
}

int Rank(Node *x, int k) {
    if(x==nil) return 1;
    int d=x->cmp(k);
    if(d==-1) return x->ch[0]->s+1;
    else if(!d) return Rank(x->ch[0], k);
    else return Rank(x->ch[1], k)+x->ch[0]->s+x->c;
}
int kth(Node *x, int k) {
    if(k<=x->ch[0]->s) return kth(x->ch[0], k);
    else if(k<=x->ch[0]->s+x->c) return x->val;
    else return kth(x->ch[1], k-x->ch[0]->s-x->c);
}

int main() {
    ini();
    int q, opt, x; 
    gn(q);
    while(q--) {
        gn(opt), gn(x);
        if(opt==1) ins(rt, x), tot++, rebuild();
        else if(opt==2) del(rt, x), deled++, rebuild();
        else if(opt==3) printf("%d\n", Rank(rt, x));
        else if(opt==4) printf("%d\n", kth(rt, x));
        else if(opt==5) printf("%d\n", kth(rt, Rank(rt, x)-1));
        else if(opt==6) printf("%d\n", kth(rt, Rank(rt, x+1)));
    }
    return 0;
}