FHQ Treap

在竞赛中我们一般使用FHQ Treap这种弱平衡的二叉搜索树。(又称无旋Treap)

它只有分裂与合并两种操作，相当好写。

#include<bits/stdc++.h>
using namespace std;
const int N=1e6+7;
mt19937 rd(time(0));
struct node{
    int l,r,val,pri,size;
}t[N];
int cnt,root;
int newnode(int x){
    cnt++;
    t[cnt].l=t[cnt].r=0;
    t[cnt].size=1;
    t[cnt].val=x;
    t[cnt].pri=rd();
    return cnt;
}
void update(int u){
    t[u].size=t[t[u].l].size+t[t[u].r].size+1;
    return ;
}
void split(int u,int x,int &l,int &r){
    if(u==0){
        l=r=0;
        return ;
    }
    if(t[u].val<=x){
        l=u;
        split(t[u].r,x,t[u].r,r);
    }else {
        r=u;
        split(t[u].l,x,l,t[u].l);
    }
    update(u);
    return ;
}
int merge(int l,int r){
    if(!l||!r)return r+l;
    if(t[l].pri>t[r].pri){
        t[l].r=merge(t[l].r,r);
        update(l);
        return l;
    }else {
        t[r].l=merge(l,t[r].l);
        update(r);
        return r;
    }
}
void insert(int x){
    int l,r;
    split(root,x,l,r);
    root=merge(merge(l,newnode(x)),r);
    return ;
}
void del(int x){
    int l,r,p;
    split(root,x,l,r);
    split(l,x-1,l,p);
    p=merge(t[p].l,t[p].r);
    root=merge(merge(l,p),r);
    return ;
}
void xth(int x){
    int l,r;
    split(root,x-1,l,r);
    cout<<t[l].size+1<<'\n';
    root=merge(l,r);
    return ;
}
int kth(int u,int k){
    if(k==t[t[u].l].size+1)return u;
    if(k<=t[t[u].l].size)return kth(t[u].l,k);
    else return kth(t[u].r,k-t[t[u].l].size-1);
}
void preor(int x){
    int l,r;
    split(root,x-1,l,r);
    cout<<t[kth(l,t[l].size)].val<<'\n';
    root=merge(l,r);
    return ;
}
void sucor(int x){
    int l,r;
    split(root,x,l,r);
    cout<<t[kth(r,1)].val<<'\n';
    root=merge(l,r);
    return ;
}
int main(){
    int n;
    cin>>n;
    while(n--){
        int opt,x;
        cin>>opt>>x;
        if(opt==1)insert(x);
        else if(opt==2)del(x);
        else if(opt==3)xth(x);
        else if(opt==4)cout<<t[kth(root,x)].val<<'\n';
        else if(opt==5)preor(x);
        else sucor(x);
    }
    return 0;
}

01trie：

# include <bits/stdc++.h>
using namespace std;
namespace trees
{
	template <const int N>
	class trie
	{
		private :
			struct node
			{
				int ch[2];
				int val;
			}tree[300012];
			int id = 2;
			int add ()
			{
				tree[id].ch[0] = 0;
				tree[id].ch[1] = 0;
				tree[id].val = 0;
				return id ++;
			}
		public :
			void insert (int x)
			{
				int u = 1;
				for (int i = 25; i >= 0; i --)
				{
					short v = (x >> i) & 1;
					if (!tree[u].ch[v]) tree[u].ch[v] = add ();
					u = tree[u].ch[v];
					tree[u].val += 1;
				}
			}
			void del (int x)
			{
				int u = 1;
				for (int i = 25; i >= 0; i --)
				{
					short v = (x >> i) & 1;
					if (!u) tree[u].ch[v] = add ();
					u = tree[u].ch[v];
					if (tree[u].val)
					{
						tree[u].val -= 1;
					}
				}
			}
			int rank (int x)
			{
				int ret = 0, u = 1;
				for (int i = 25; i >= 0; i --)
				{
					short v = (x >> i) & 1;
					if (v)
					{
						ret += tree[tree[u].ch[0]].val;
						u = tree[u].ch[1];
					}
					else
					{
						u = tree[u].ch[0];
					}
					if (!u) break;
				}
				return ret;
			}
			int find_by_order (int x)
			{
				int ret = 0, u = 1;
				for (int i = 25; i >= 0; i --)
				{
//					if (!x) break;
//					cout << u << ' ' << tree[u].val << endl;
					if (tree[tree[u].ch[0]].val >= x)
					{
						u = tree[u].ch[0];
					}
					else
					{
						ret |= (1 << i);
						x -= tree[tree[u].ch[0]].val;
						u = tree[u].ch[1];
					}
				}
				return ret;
			}
			int lower_bound (int x)
			{
				return find_by_order (rank (x));
			}
			int upper_bound (int x)
			{
				return find_by_order (rank (x + 1) + 1);
			}
	};
}
using namespace trees;
int n;
trie <100012> tree;
const int num = 1e7;
int main ()
{
	ios :: sync_with_stdio (0);
	cin.tie (0), cout.tie (0);
	cin >> n;
	do
	{
		int op, x;
		cin >> op >> x;
		switch (op)
		{
			case 1 :
			{
				tree.insert (x + num);
//				cout << "num : 1" << endl;
				break;
			}
			case 2 :
			{
				tree.del (x + num);
//				cout << "num : 2" << endl;
				break;
			}
			case 3 :
			{
				cout << tree.rank (x + num) + 1 << endl;
//				cout << "num : 3" << endl;
				break;
			}
			case 4 :
			{
				cout << tree.find_by_order (x) - num << endl;
//				cout << "num : 4" << endl;
				break;
			}
			case 5 :
			{
				cout << tree.lower_bound (x + num) - num << endl;
//				cout << "num : 5" << endl;
				break;
			}
			case 6 :
			{
				cout << tree.upper_bound (x + num) - num << endl;
//				cout << "num : 6" << endl;
				break;
			}
		}
	} while (-- n);
}