第K小数
Description
现在已有N个整数，你有以下三种操作：
1 A：表示加入一个值为A的整数；
2 B：表示删除其中值为B的整数；
3 K：表示输出这些整数中第K小的数；
Input
第一行，两个整数N，M，表示最开始有N个整数，总共有M个操作
第二行用空格隔开的N个整数
接下来M行，每行表示一个操作
Output
若干行，一行一个整数，表示所求的第K小的数字
Sample Input
5 5
6 2 7 4 9
1 8
1 6
3 10
2 4
3 3
Sample Output
0
7
Hint
【注意】：如果有多个大小相同的数字，只把他们看做一个数字，如样例。 若找不到第K小的数，输出0
【数据范围】
0<=N<=2,000,000
M<=1,000,000
-1,000,000,000<=每个整数<=1,000,000,000
写个普通的treap就好
/*by SilverN*/
#include<iostream>
#include<cstdio>
#include<cmath>
#include<cstring>
#include<algorithm>
using namespace std;
int n,m;
struct treap{
int l,r;//左右子树
int val,ct;//值 重复次数
int size,rand;//管控数量，随机权值
}t[];
int root=,cnt=;
int ans;
void update(int k){
t[k].size=t[t[k].l].size+t[t[k].r].size+t[k].ct;
}
void lt(int &k){//左旋
int now=t[k].r;
t[k].r=t[now].l;
t[now].l=k;
t[now].size=t[k].size;
update(k);
k=now;
return;
}
void rt(int &k){
int now=t[k].l;
t[k].l=t[now].r;
t[now].r=k;
t[now].size=t[k].size;
update(k);
k=now;
return;
}
void insert(int &k,int x){
if(k==){
t[++cnt].val=x;
t[cnt].size=;
t[cnt].ct=;
t[cnt].rand=rand();
k=cnt;
return;
}
t[k].size++;
if(t[k].val==x) return;//多个重复数字看做一个
else if(x>t[k].val){
insert(t[k].r,x);
if(t[t[k].r].rand<t[k].rand) lt(k);
}else{//x<t[k].val
insert(t[k].l,x);
if(t[t[k].l].rand<t[k].rand) rt(k);
}
return;
}
void del(int &k,int x){
if(k==)return;
if(t[k].val==x){
if(t[k].ct>){t[k].ct--;t[k].size--;return;}
if(t[k].l*t[k].r==)k=t[k].l+t[k].r;//如果k是链结点(只有一个子节点)，由其子节点补位
else{
if(t[t[k].l].rand<t[t[k].r].rand){
rt(k);
del(k,x);
}
else{
lt(k);
del(k,x);
}
}
return;
}
t[k].size--;
if(x>t[k].val)del(t[k].r,x);
if(x<t[k].val)del(t[k].l,x);
return;
}
int ask_num(int k,int x){// 已知排名问数字
if(!k)return ;
if(x<=t[t[k].l].size)return ask_num(t[k].l,x);//排名小于左子树包含结点数量，则往左查
if(x>t[t[k].l].size+t[k].ct)return ask_num(t[k].r,x-t[t[k].l].size-t[k].ct);
//排名大于“左子树结点数加父结点重复数”，则往右查
else return t[k].val;//否则返回父结点值
}
int main(){
int opt,x;
scanf("%d%d",&n,&m);
for(int i=;i<=n;i++){
scanf("%d",&x);
insert(root,x);
}
while(m--){
scanf("%d%d",&opt,&x);
switch(opt){
case : insert(root,x); break;
case : del(root,x); break;
case : printf("%d\n",ask_num(root,x));break;
}
// for(int i=1;i<=cnt;i++)printf("%d ",t[i].val);
// cout<<endl;
}
return ;
}