这是一道treap的模板题，不要问我为什么一直在写模板题
依旧只放代码
Treap 版
//SPOJ 3273
//by Cydiater
//2016.8.31
#include <iostream>
#include <cstring>
#include <ctime>
#include <cmath>
#include <cstdlib>
#include <string>
#include <algorithm>
#include <queue>
#include <map>
#include <iomanip>
#include <cstdio>
using namespace std;
#define ll long long
#define up(i,j,n) for(int i=j;i<=n;i++)
#define down(i,j,n) for(int i=j;i>=n;i--)
;
const int oo=0x3f3f3f3f;
inline int read(){
,f=;
;ch=getchar();}
+ch-';ch=getchar();}
return x*f;
}
,tol=;
char op;
map<int,int>m;
struct node{
int rnd,v,cnt,siz,leftt,rightt;
}t[MAXN];
namespace solution{
void updata(int k){
t[k].siz=t[t[k].leftt].siz+t[t[k].rightt].siz+t[k].cnt;
}
void lefturn(int &k){
int tt=t[k].rightt;t[k].rightt=t[tt].leftt;t[tt].leftt=k;
t[tt].siz=t[k].siz;updata(k);k=tt;
}
void righturn(int &k){
int tt=t[k].leftt;t[k].leftt=t[tt].rightt;t[tt].rightt=k;
t[tt].siz=t[k].siz;updata(k);k=tt;
}
void insert(int &k,int x){
){
k=++tol;t[k].leftt=t[k].rightt=;
t[k].cnt=;t[k].siz=;t[k].v=x;
t[k].rnd=rand();
return;
}
t[k].siz++;
if(t[k].v==x)t[k].cnt++;
else if(x>t[k].v){
insert(t[k].rightt,x);
if(t[t[k].rightt].rnd<t[k].rnd)lefturn(k);
}else if(x<t[k].v){
insert(t[k].leftt,x);
if(t[t[k].leftt].rnd<t[k].rnd)righturn(k);
}
}
void del(int &k,int x){
) return;
if(x==t[k].v){
){t[k].siz--;t[k].cnt--;return;}
) k=t[k].leftt+t[k].rightt;
else if(t[t[k].leftt].rnd<t[t[k].rightt].rnd){
righturn(k);
del(k,x);
}
else if(t[t[k].leftt].rnd>t[t[k].rightt].rnd){
lefturn(k);
del(k,x);
}
}else if(x>t[k].v){
t[k].siz--;
del(t[k].rightt,x);
}else if(x<t[k].v){
t[k].siz--;
del(t[k].leftt,x);
}
}
int query_num(int k,int x){
) return oo;
if(x<=t[t[k].leftt].siz) return query_num(t[k].leftt,x);
else if(x>t[t[k].leftt].siz+t[k].cnt) return query_num(t[k].rightt,x-(t[t[k].leftt].siz+t[k].cnt));
else return t[k].v;
}
int query_siz(int k,int x){
) ;
if(x<=t[k].v) return query_siz(t[k].leftt,x);
else if(x>t[k].v) return t[t[k].leftt].siz+t[k].cnt+query_siz(t[k].rightt,x);
}
void slove(){
N=read();
while(N--){
scanf("%c",&op);num=read();
){insert(root,num);m[num]=;}
){del(root,num);m[num]=;}
if(op=='K'){
if(num>t[root].siz)puts("invalid");
else{
int ans=query_num(root,num);
if(ans>=oo){
puts("invalid");
continue;
}
printf("%d\n",ans);
}
}
if(op=='C')printf("%d\n",query_siz(root,num));
}
}
}
int main(){
//freopen("input.in","r",stdin);
using namespace solution;
slove();
;
}Splay 版：
splay会被卡掉..0.3s貌似扛不住了，不过过了前几组，先粘上来吧
//SPOJ 3273
//by Cydiater
//2016.9.4
#include <iostream>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <string>
#include <iomanip>
#include <ctime>
#include <cmath>
#include <iomanip>
#include <queue>
#include <map>
using namespace std;
#define ll long long
#define up(i,j,n) for(int i=j;i<=n;i++)
#define down(i,j,n) for(int i=j;i>=n;i--)
;
const int oo=0x3f3f3f3f;
;
;
inline int read(){
,f=;
;ch=getchar();}
+ch-';ch=getchar();}
return x*f;
}
char op;
,root=,num,N;
struct SpalyTree{
],siz,cnt,v,fa;
}t[MAXN];
struct Hash{
int Num[MAXN];
Hash(){up(i,,MAXN-)Num[i]=-oo;}
void insert(int x){
int tmp=x%mod;
||Num[tmp]!=-oo){tmp+=step;tmp%=mod;}
Num[tmp]=x;
}
bool Get(int x){
){hashvalue+=step;hashvalue%=mod;}
while(Num[hashvalue]!=x&&Num[hashvalue]!=-oo){hashvalue+=step;hashvalue%=mod;}
;
;
}
void del(int x){
int tmp=x%mod;
||Num[tmp]!=x){tmp+=step;tmp%=mod;}
Num[tmp]=;
}
}lable;
namespace solution{
void updata(int x){
if(x){
t[x].siz=t[x].cnt;
])t[x].siz+=t[t[x].son[]].siz;
])t[x].siz+=t[t[x].son[]].siz;
}
}
]==x;}
]=t[x].son[]=t[x].fa=t[x].siz=t[x].cnt=t[x].v=;}
void rotate(int x){
int old=t[x].fa,oldf=t[old].fa,which=get(x);
t[old].son[which]=t[x].son[which^];t[t[old].son[which]].fa=old;
t[old].fa=x;t[x].son[which^]=old;
t[x].fa=oldf;
]==old]=x;
updata(old);updata(x);
}
void splay(int x){
for(int fa;(fa=t[x].fa);rotate(x))if(t[fa].fa)
rotate((get(x)==get(fa)?fa:x));root=x;
}
void insert(int x){
){
root=++tol;
t[root].son[]=t[root].son[]=t[root].fa=;
t[root].v=x;t[root].cnt=t[root].siz=;
return;
}
;
){
if(t[now].v==x){
t[now].cnt++;
updata(now);updata(fa);
splay(now);break;
}
fa=now;now=t[now].son[x>t[now].v];
){
now=++tol;
t[now].son[]=t[now].son[]=;t[now].v=x;
t[now].siz=t[now].cnt=;t[now].fa=fa;
t[fa].son[x>t[fa].v]=tol;
updata(fa);splay(now);break;
}
}
}
int find(int v){
,now=root;
){
];
else{
ans+=(t[now].son[]?t[t[now].son[]].siz:);
if(v==t[now].v){
splay(now);
;
}
ans+=t[now].cnt;
now=t[now].son[];
}
}
}
int pre(){
];
])now=t[now].son[];
return now;
}
int match_rank(int x){
int now=root;
){
]&&x<=t[t[now].son[]].siz)now=t[now].son[];
else{
]?t[t[now].son[]].siz:)+t[now].cnt;
if(x<=tmp) return t[now].v;
x-=tmp;now=t[now].son[];
}
}
}
void del(int x){
int whatever=find(x);
){
t[root].cnt--;
t[root].siz--;
return;
}
]+t[root].son[]==){
clear(root);root=;
return;
}
]){
];t[root].fa=;
clear(oldroot);return;
}]){
];t[root].fa=;
clear(oldroot);return;
}
int leftbig=pre(),oldroot=root;
splay(leftbig);
t[t[oldroot].son[]].fa=root;
t[root].son[]=t[oldroot].son[];
clear(oldroot);
updata(root);
}
int get_siz(int num){
int now=root;
){
]].siz+t[now].cnt;
];
}
}
}
int main(){
//freopen("input.in","r",stdin);
using namespace solution;
N=read();
while(N--){
scanf("%c",&op);num=read();
){insert(num);lable.insert(num);}
){del(num);lable.del(num);}
if(op=='K'){
if(num>t[root].siz)puts("invalid");
else printf("%d\n",match_rank(num));
}
if(op=='C')printf("%d\n",get_siz(num));
}
;
}