Description
您需要写一种数据结构（可参考题目标题），来维护一些数，其中需要提供以下操作：
1. 插入x数
2. 删除x数(若有多个相同的数，因只删除一个)
3. 查询x数的排名(若有多个相同的数，因输出最小的排名)
4. 查询排名为x的数
5. 求x的前驱(前驱定义为小于x，且最大的数)
6. 求x的后继(后继定义为大于x，且最小的数)
(nleqslant 1 imes 10^5)
Solution
Treap.
因为之前的Treap是用指针写的,现在都改成数组了...
一开始写了个Splay...T的飞起...
Code
/**************************************************************
Problem: 3224
User: BeiYu
Language: C++
Result: Accepted
Time:404 ms
Memory:4032 kb
****************************************************************/
#include <bits/stdc++.h>
using namespace std;
#define debug(a) cout<<(#a)<<"="<<a<<" "
#define lc(o) ch[o][0]
#define rc(o) ch[o][1]
#define uor(i,j,k) for(int i=j;i<=(int)k;i++)
#define uep(i,j,k) for(int i=j;i<(int)k;i++)
#define dor(i,j,k) for(int i=j;i>=(int)k;i--)
typedef long long ll;
typedef pair<int,int> pr;
typedef vector<int> vi;
typedef vector<ll> vl;
typedef vector<string> vs;
const int N = 100050;
const int M = 25;
const int oo = 0x3fffffff;
const ll OO = 1e18;
const ll p = 1000000007;
ll Pow(ll a,ll b,ll r=1) { for(;b;b>>=1,a=a*a%p) if(b&1) r=r*a%p;return r; }
ll Pow(ll a,ll b,ll p,ll r=1) { for(;b;b>>=1,a=a*a%p) if(b&1) r=r*a%p;return r; }
ll inv(ll x) { return Pow(x,p-2); }
void Add(ll &x,ll y) { x=(x+y%p)%p; }
void Sub(ll &x,ll y) { x=(x-y%p+p)%p; }
void Mul(ll &x,ll y) { x=x*(y%p)%p; }
int chkmax(ll &x,ll y) { return x<y?x=y,1:0; }
int chkmin(ll &x,ll y) { return x>y?x=y,1:0; }
inline ll in(ll x=0,char ch=getchar(),int v=1) {
while(ch>'9' || ch<'0') v=ch=='-'?-1:v,ch=getchar();
while(ch>='0' && ch<='9') x=x*10+ch-'0',ch=getchar();
return x*v;
}
/*end*/
namespace Treap {
int cp,rt;
int sz[N],ss[N],ch[N][2],f[N],rv[N];
int val[N];
int Newnode(int v) {
++cp,ss[cp]=sz[cp]=1,f[cp]=lc(cp)=rc(cp)=0,val[cp]=v,rv[cp]=rand();
return cp;
}
void init() { rt=0,rv[0]=-oo; }
void Update(int o) { sz[o]=sz[lc(o)]+sz[rc(o)]+ss[o]; }
void Rot(int &o,int d) {
int t=ch[o][d];ch[o][d]=ch[t][d^1],ch[t][d^1]=o,Update(o),Update(t),o=t;
}
void insert(int &o,int v) {
if(!o) { o=Newnode(v);return; }
if(val[o]==v) { ss[o]++,Update(o);return; }
int d=v>val[o];
insert(ch[o][d],v);
if(rv[ch[o][d]]>rv[o]) Rot(o,d);
else Update(o);
}
void earse(int &o,int v) {
if(val[o]==v) {
if(ss[o]>1) { ss[o]--,Update(o);return; }
int d=rv[lc(o)]<rv[rc(o)];
if(!ch[o][d]) { o=0;return; }
Rot(o,d),earse(ch[o][d^1],v);
}else earse(ch[o][v>val[o]],v);
Update(o);
}
int rk(int o,int v) {
if(val[o]<v) return sz[lc(o)]+ss[o]+rk(rc(o),v);
else if(val[o]>v) return rk(lc(o),v);
else return sz[lc(o)];
}
int kth(int o,int k) {
if(sz[lc(o)]>=k) return kth(lc(o),k);
else if(sz[lc(o)]+ss[o]<k) return kth(rc(o),k-sz[lc(o)]-ss[o]);
else return val[o];
}
int pre(int o,int v) {
if(!o) return -oo;
if(val[o]>=v) return pre(lc(o),v);
else return max(val[o],pre(rc(o),v));
}
int nxt(int o,int v) {
if(!o) return oo;
if(val[o]<=v) return nxt(rc(o),v);
else return min(val[o],nxt(lc(o),v));
}
void insert(int v) { insert(rt,v); }
void earse(int v) { earse(rt,v); }
int rk(int v) { return rk(rt,v); }
int kth(int k) { return kth(rt,k); }
int pre(int v) { return pre(rt,v); }
int nxt(int v) { return nxt(rt,v); }
};
int main() {
Treap::init();
for(int T=in();T--;) {
int opt=in(),x=in();
switch(opt) {
case 1:Treap::insert(x);break;
case 2:Treap::earse(x);break;
case 3:printf("%d
",Treap::rk(x)+1);break;
case 4:printf("%d
",Treap::kth(x));break;
case 5:printf("%d
",Treap::pre(x));break;
case 6:printf("%d
",Treap::nxt(x));break;
}
}
return 0;
}