treap做法，参考hzwer的博客
#include <iostream>
#include <cstdlib>
#include <cstdio>
using namespace std;
int n, opt, uu, rot, cnt, ans;
struct Treap{
int siz[100005], hav[100005], val[100005], rnd[100005], l[100005], r[100005];
void upd(int x){
siz[x] = siz[l[x]] + siz[r[x]] + hav[x];
}
void lRotate(int &k){
int t=r[k]; r[k] = l[t]; l[t] = k;
siz[t] = siz[k]; upd(k); k = t;
}
void rRotate(int &k){
int t=l[k]; l[k] = r[t]; r[t] = k;
siz[t] = siz[k]; upd(k); k = t;
}
void insert(int &k, int x){
if(!k){
k = ++cnt; siz[k] = hav[k] = 1;
val[k] = x; rnd[k] = rand();
return ;
}
siz[k]++;
if(val[k]==x) hav[k]++;
else if(val[k]<x){
insert(r[k], x);
if(rnd[r[k]]<rnd[k]) lRotate(k);
}
else{
insert(l[k], x);
if(rnd[l[k]]<rnd[k]) rRotate(k);
}
}
void shanchu(int &k, int x){
if(!k) return ;
if(val[k]==x){
if(hav[k]>1){
hav[k]--; siz[k]--;
return ;
}
else if(l[k]*r[k]==0) k = l[k] + r[k];
else if(rnd[l[k]]>rnd[r[k]])
lRotate(k), shanchu(k, x);
else
rRotate(k), shanchu(k, x);
}
else if(val[k]<x) siz[k]--, shanchu(r[k], x);
else siz[k]--, shanchu(l[k], x);
}
int queryRank(int k, int x){
if(x<val[k]) return queryRank(l[k], x);
else if(x>val[k]) return queryRank(r[k], x)+siz[l[k]]+hav[k];
else return siz[l[k]]+1;
}
int queryNum(int k, int x){
if(x<=siz[l[k]]) return queryNum(l[k], x);
else if(x>siz[l[k]]+hav[k]) return queryNum(r[k], x-siz[l[k]]-hav[k]);
else return val[k];
}
void queryPre(int k, int x){
if(!k) return ;
if(val[k]<x) ans = k, queryPre(r[k], x);
else queryPre(l[k], x);
}
void queryNxt(int k, int x){
if(!k) return ;
if(val[k]>x) ans = k, queryNxt(l[k], x);
else queryNxt(r[k], x);
}
}treap;
int main(){
cin>>n;
while(n--){
scanf("%d %d", &opt, &uu);
switch(opt){
case 1: treap.insert(rot, uu); break;
case 2: treap.shanchu(rot, uu); break;
case 3: printf("%d
", treap.queryRank(rot, uu)); break;
case 4: printf("%d
", treap.queryNum(rot, uu)); break;
case 5: treap.queryPre(rot, uu); printf("%d
", treap.val[ans]); break;
case 6: treap.queryNxt(rot, uu); printf("%d
", treap.val[ans]); break;
}
}
return 0;
}
splay做法，参照zyf2000，但是一般我们用splay都是维护区间的
#include <iostream>
#include <cstdio>
using namespace std;
int n, uu, vv, rot=0, sze=0;
struct Splay{
int s[100005][2], f[100005], siz[100005], cnt[100005], val[100005];
inline void clr(int x){
s[x][0] = s[x][1] = f[x] = siz[x] = cnt[x] = val[x] = 0;
}
inline void upd(int x){
siz[x] = siz[s[x][0]] + siz[s[x][1]] + cnt[x];
}
inline int gx(int x){
return s[f[x]][1]==x;
}
void rotate(int x){
int old=f[x], oldf=f[old], w=gx(x);
s[old][w] = s[x][w^1]; s[x][w^1] = old;
f[s[old][w]] = old; f[old] = x; f[x] = oldf;
if(oldf) s[oldf][s[oldf][1]==old] = x;
upd(x); upd(old);
}
void splay(int x){
int fa=1;
while(fa){
fa = f[x];
if(!fa) break;
if(f[fa])rotate((gx(x)==gx(fa))?fa:x);
rotate(x);
}
rot = x;
}
void ins(int x){
if(!rot){
rot = ++sze; clr(rot);
siz[rot] = cnt[rot] = 1; val[rot] = x;
return ;
}
int now=rot, fa=0;
while(now){
if(val[now]==x){
cnt[now]++; upd(now);
upd(f[now]); splay(now); return ;
}
fa = now; now = s[now][val[now]<x];
if(!now){
now = ++sze; clr(now); val[now] = x; cnt[now] = siz[now] = 1;
f[now] = fa; s[fa][val[fa]<x] = now; upd(fa); splay(sze);
break;
}
}
}
int getRank(int x){
int now=rot, ans=0;
while(now){
if(x<val[now]) now = s[now][0];
else{
ans += siz[s[now][0]];
if(val[now]==x){
splay(now);
return ans+1;
}
ans += cnt[now];
now = s[now][1];
}
}
}
int getNum(int x){
int now=rot;
while(now){
if(x<=siz[s[now][0]]) now = s[now][0];
else{
int temp=siz[s[now][0]]+cnt[now];
if(x<=temp) return val[now];
x -= temp; now = s[now][1];
}
}
}
int getPre(){
int now=s[rot][0];
while(s[now][1]) now = s[now][1];
return now;
}
int getNxt(){
int now=s[rot][1];
while(s[now][0]) now = s[now][0];
return now;
}
void del(int x){
getRank(x);
if(cnt[rot]>1){
cnt[rot]--; upd(rot);
return ;
}
if(!s[rot][0] && !s[rot][1]){
clr(rot); rot = sze = 0;
return ;
}
if(!s[rot][0]){
int oldr=rot; rot = s[rot][1]; f[rot] = 0; clr(oldr);
return ;
}
if(!s[rot][1]){
int oldr=rot; rot = s[rot][0]; f[rot] = 0; clr(oldr);
return ;
}
int leftBig=getPre(), oldr=rot;
splay(leftBig); s[rot][1] = s[oldr][1];
f[s[rot][1]] = rot; clr(oldr); upd(rot);
}
}splay;
int main(){
cin>>n;
while(n--){
scanf("%d %d", &uu, &vv);
switch(uu){
case 1: splay.ins(vv); break;
case 2: splay.del(vv); break;
case 3: printf("%d
", splay.getRank(vv)); break;
case 4: printf("%d
", splay.getNum(vv)); break;
case 5: splay.ins(vv); printf("%d
", splay.val[splay.getPre()]); splay.del(vv); break;
case 6: splay.ins(vv); printf("%d
", splay.val[splay.getNxt()]); splay.del(vv); break;
}
}
return 0;
}