111006 - 普通平衡树

收集了四种做法。 (代码 by郭沣)

vector

#include <bits/stdc++.h>
using namespace std;
const int maxn=200006;
inline int read() {
	int x=0,c=getchar();
	bool f=1;
	while(c<=47||c>=58) {
		f=f&&(c^45);
		c=getchar();
	}
	while(c>=48&&c<=57) {
		x=(x<<3)+(x<<1)+(c&15);
		c=getchar();
	}
	return f?x:-x;
}
int main() {
	int n=read();
	vector<int>v;
	v.reserve(200000);
	int f,x;
	for(int i=1; i<=n; ++i) {
		f=read(),x=read();
		if(f==1)v.insert(upper_bound(v.begin(),v.end(),x),x);
		else if(f==2)v.erase(lower_bound(v.begin(),v.end(),x));
		else if(f==3)printf("%d\n",lower_bound(v.begin(),v.end(),x)-v.begin()+1);
		else if(f==4)printf("%d\n",v[x-1]);
		else if(f==5)printf("%d\n",*--lower_bound(v.begin(),v.end(),x));
		else if(f==6)printf("%d\n",*upper_bound(v.begin(),v.end(),x));
	}
	return 0;
}

splay

#include <bits/stdc++.h>
using namespace std;
int read() {
    int x=0,c=getchar();
    bool f=1;
    while(c<=47||c>=58) {
        f=f&&(c^45);
        c=getchar();
    }
    while(c>=48&&c<=57) {
        x=(x<<3)+(x<<1)+(c&15);
        c=getchar();
    }
    return f?x:-x;
}
template<typename T=int>
class splay_tree {
    private:
        struct Point {
            T val;
            int siz;
            int cnt;
            int son[2],fa;
            Point() {
                siz=cnt=son[0]=son[1]=fa=0;
            }
            Point(const T val) {
                this->val=val;
                siz=cnt=1;
                son[0]=son[1]=fa=0;
            }
        } tr[3<<19];
        int siz,length,root;
        bool get_id(const int x) {
            return tr[tr[x].fa].son[0]^x;
        }
        const void upto(const int x) {
            tr[x].siz=tr[tr[x].son[0]].siz+tr[tr[x].son[1]].siz+tr[x].cnt;
        }
        const void connect(const int x,const int fa,const bool id) {
            tr[x].fa=fa;
            tr[fa].son[id]=x;
        }
        const void rotate(const int x) {
            const int y=tr[x].fa,z=tr[y].fa;
            const bool id=get_id(x),mid=get_id(y);
            connect(tr[x].son[!id],y,id);
            upto(y);
            connect(y,x,!id);
            upto(x);
            connect(x,z,mid);
        }
        const void splay(const int x,int rt) {
            rt=tr[rt].fa;
            while(tr[x].fa^rt)
                if(tr[tr[x].fa].fa==rt)
                    rotate(x);
                else if(get_id(x)^get_id(tr[x].fa))
                    rotate(x),rotate(x);
                else
                    rotate(tr[x].fa),rotate(x);
        }
        const void Splay(const int x) {
            splay(x,root);
            root=x;
        }
    public:
        splay_tree() {
            siz=length=root=0;
        }
        const void push(const T x) {
            if(!siz++) {
                tr[root=++length]=Point(x);
                connect(root,0,0);
                return;
            }
            for(int i=root; 1; ++tr[i].siz)
                if(tr[i].val==x) {
                    ++tr[i].cnt;
                    Splay(i);
                    return;
                } else {
                    bool id=tr[i].val<x;
                    if(!tr[i].son[id]) {
                        tr[++length]=Point(x);
                        connect(length,i,id);
                        Splay(length);
                        return;
                    } else i=tr[i].son[id];
                }
        }
        const void pop(const T x) {
            --siz;
            for(int i=root; tr[i].siz--; i=tr[i].son[x>tr[i].val])
                if(tr[i].val==x) {
                    if(--tr[i].cnt) {
                        Splay(i);
                        return;
                    }
                    Splay(i);
                    if(!tr[i].son[0]) {
                        root=tr[i].son[1];
                        connect(tr[i].son[1],0,0);
                        return;
                    }
                    if(!tr[i].son[1]) {
                        root=tr[i].son[0];
                        connect(tr[i].son[0],0,0);
                        return;
                    }
                    int j=tr[i].son[0];
                    while(tr[j].son[1])
                        j=tr[j].son[1];
                    splay(j,tr[i].son[0]);
                    connect(tr[i].son[1],tr[i].son[0],1);
                    root=tr[i].son[0];
                    connect(tr[i].son[0],0,0);
                    return;
                }
        }
        int rank(const T x) {
            int rt=1;
            for(int i=root; i;)
                if(tr[i].val==x) {
                    Splay(i);
                    return tr[tr[i].son[0]].siz+1;
                } else if(tr[i].val<x) {
                    rt+=tr[tr[i].son[0]].siz+tr[i].cnt;
                    i=tr[i].son[1];
                } else
                    i=tr[i].son[0];
            return rt;
        }
        T atrank(int x) {
            int r(1);
            for(int i=root; true;) {
                if(r+tr[tr[i].son[0]].siz<=x&&x<r+tr[tr[i].son[0]].siz+tr[i].cnt) {
                    Splay(i);
                    return tr[i].val;
                } else if(x<r+tr[tr[i].son[0]].siz)
                    i=tr[i].son[0];
                else
                    r+=tr[tr[i].son[0]].siz+tr[i].cnt,i=tr[i].son[1];
            }
        }
        T pre(const T x) {
            T r;
            int li;
            for(int i=root; i;)
                if(tr[i].val>=x)li=i,i=tr[i].son[0];
                else r=tr[li=i].val,i=tr[i].son[1];
            Splay(li);
            return r;
        }
        T ne(const T x) {
            T r;
            int li;
            for(int i=root; i;)
                if(tr[i].val<=x)li=i,i=tr[i].son[1];
                else r=tr[li=i].val,i=tr[i].son[0];
            Splay(li);
            return r;
        }
};
splay_tree<int>tr;
int m,n,lastans,ans,x,k;
int main() {
    n=read();
    while(n--) {
        x=read(),k=read();
        if(!(x^1))tr.push(k);
        else if(!(x^2))tr.pop(k);
        else if(!(x^3))lastans=tr.rank(k),printf("%d\n",lastans);
        else if(!(x^4))lastans=tr.atrank(k),printf("%d\n",lastans);
        else if(!(x^5))lastans=tr.pre(k),printf("%d\n",lastans);
        else if(!(x^6))lastans=tr.ne(k),printf("%d\n",lastans);
    }
    return 0;
}

fhq treap

#include <bits/stdc++.h>
using namespace std;
const int MAXN=1100015;
inline int read() {
    static int x,c=getchar(),f;
    for(f=1; c<=47||c>=58; c=getchar())f=f&&(c^45);
    for(x=0; c>=48&&c<=57; c=getchar())x=(x<<3)+(x<<1)+(c&15);
    return f?x:-x;
}
struct node {
    int a,b;
    node(int x=0,int y=0) {
        a=x,b=y;
    }
};
int key[MAXN],w[MAXN],siz[MAXN],son[MAXN][2];
int n,m,ans,root,lst,cnt;
inline void push_up(int u) {
    siz[u]=siz[son[u][0]]+siz[son[u][1]]+1;
}
node split(int u,int k) {
    if(!u) return node(0,0);
    if(key[u]<k) {
        node t=split(son[u][1],k);
        son[u][1]=t.a;
        push_up(u);
        return node(u,t.b);
    }
    node t=split(son[u][0],k);
    son[u][0]=t.b;
    push_up(u);
    return node(t.a,u);
}
int merge(int u,int v) {
    if(!u||!v) return u|v;
    if(w[u]<w[v]) {
        son[u][1]=merge(son[u][1],v);
        push_up(u);
        return u;
    }
    son[v][0]=merge(u,son[v][0]);
    push_up(v);
    return v;
}
void push(int v) {
    key[++cnt]=v,w[cnt]=rand(),siz[cnt]=1;
    node t=split(root,v);
    root=merge(merge(t.a,cnt),t.b);
}
void pop(int v) {
    node x=split(root,v),y=split(x.b,v+1);
    y.a=merge(son[y.a][0],son[y.a][1]);
    root=merge(x.a,merge(y.a,y.b));
}
int rnk(int v) {
    node t=split(root,v);
    int ans=siz[t.a]+1;
    root=merge(t.a,t.b);
    return ans;
}
int kth(int v) {
    int pos=root,x;
    while(x=siz[son[pos][0]],pos) {
        if(v<=x)pos=son[pos][0];
        else if(v==x+1) return key[pos];
        else pos=son[pos][1],v-=x+1;
    }
    return-1;
}
int pre(int v) {
    return kth(rnk(v)-1);
}
int suf(int v) {
    return kth(rnk(v+1));
}
int main() {
    srand(20070225);
    m=read();
    for(int i=1,op,x; i<=m; ++i) {
        op=read(),x=read();
        if(op==1)push(x);
        else if(op==2)pop(x);
        else if(op==3)lst=rnk(x);
        else if(op==4)lst=kth(x);
        else if(op==5)lst=pre(x);
        else if(op==6)lst=suf(x);
        if(3<=op&&op<=6)printf("%d\n",lst);
    }
    return 0;
}

替罪羊树

#include <bits/stdc++.h>
using namespace std;
const int MAXN=3<<19;
const double a=0.725;
int read() {
	int x=0,c=getchar();
	bool f=1;
	while(c<=47||c>=58) {
		f=f&&(c^45);
		c=getchar();
	}
	while(c>=48&&c<=57) {
		x=(x<<3)+(x<<1)+(c&15);
		c=getchar();
	}
	return f?x:-x;
}
struct tree {
	int val,siz,siz2,cnt,sum,ls,rs;
} tr[MAXN];
int t,g[MAXN],cur,rt;
const void print(int x) {
	if(tr[x].ls)print(tr[x].ls);
	if(tr[x].cnt)g[++t]=x;
	if(tr[x].rs)print(tr[x].rs);
}
const void mountain(int x) {
	tr[x].siz=tr[tr[x].ls].siz+tr[tr[x].rs].siz+(tr[x].cnt?1:0);
	tr[x].siz2=tr[tr[x].ls].siz2+tr[tr[x].rs].siz2+1;
	tr[x].sum=tr[tr[x].ls].sum+tr[tr[x].rs].sum+tr[x].cnt;
}
int build(int l,int r) {
	if(l==r) {
		tr[g[l]].ls=tr[g[l]].rs=0;
		mountain(g[l]);
		return g[l];
	}
	const int mid=l+r>>1;
	tr[g[mid]].ls=l^mid?build(l,mid-1):0;
	tr[g[mid]].rs=build(mid+1,r);
	mountain(g[mid]);
	return g[mid];
}
const void rebuild(int&x) {
	t=0;
	print(x);
	x=build(1,t);
}
bool bad(const int x) {
	return tr[x].sum&&(a*tr[x].siz2<=max(tr[tr[x].ls].siz2,tr[tr[x].rs].siz2)||a*tr[x].siz2>=tr[x].siz);
}
const void push(int&x,int v) {
	if(!x) {
		tr[x=++cur].val=v;
		tr[x].cnt=1;
		mountain(x);
		return;
	}
	if(v==tr[x].val)++tr[x].cnt;
	else if(v<tr[x].val)push(tr[x].ls,v);
	else push(tr[x].rs,v);
	mountain(x);
	if(bad(x))rebuild(x);
}
const void pop(int&x,int v) {
	if(v==tr[x].val)
		if(tr[x].cnt)--tr[x].cnt;
		else;
	else if(v<tr[x].val)pop(tr[x].ls,v);
	else pop(tr[x].rs,v);
	mountain(x);
	if(bad(x))rebuild(x);
}
int rnk(int x,int v) {
	if(!x)return 1;
	if(v==tr[x].val)return tr[tr[x].ls].sum+1;
	if(v<tr[x].val)return rnk(tr[x].ls,v);
	return tr[tr[x].ls].sum+tr[x].cnt+rnk(tr[x].rs,v);
}
int kth(int x,int k) {
	if(!x)return-1;
	if(tr[tr[x].ls].sum<k&&k<=tr[tr[x].ls].sum+tr[x].cnt)return tr[x].val;
	if(k<=tr[tr[x].ls].sum)return kth(tr[x].ls,k);
	return kth(tr[x].rs,k-tr[tr[x].ls].sum-tr[x].cnt);
}
int pre(int v) {
	return kth(rt,rnk(rt,v)-1);
}
int suf(int v) {
	return kth(rt,rnk(rt,v+1));
}
int n,q,x,lstans,ans,op;
int main() {
	q=read();
	while(q--) {
		op=read(),x=read();
		if(op==1)push(rt,x);
		else if(op==2)pop(rt,x);
		else if(op==3)lstans=rnk(rt,x);
		else if(op==4)lstans=kth(rt,x);
		else if(op==5)lstans=pre(x);
		else if(op==6)lstans=suf(x);
		if(3<=op&&op<=6)printf("%d\n",lstans);
	}
	return 0;
}