很神奇

下载了 #1 发现输出一模一样还是 WA 了

评测记录

//【模板】Treap 
#include<bits/stdc++.h>
#define MAXN 100005
using namespace std;
inline void read(int &n){
	int s=0,t=1;
	char c=getchar();
	while(c<'0'||c>'9'){
		if(c=='-') t=-1;
		c=getchar();
	}
	while(c>='0'&&c<='9'){
		s=(s<<3)+(s<<1)+(c^48);c=getchar();
	}
	n=s*t;
}
inline void put(int n){
	if(n<0) n=-n;
	if(n<10){
		putchar(n+48);return;
	}
	put(n/10);putchar(n%10+48);
}
struct node{
	int l,r,val,siz,pri;
}t[MAXN];
int root,cnt;
inline void rotate(int &rt,int op){
	int son;
	if(!op){
		son=t[rt].l;
		t[son].siz=t[rt].siz;
		t[rt].siz-=t[t[rt].l].siz;
		t[rt].l=t[son].r;
		t[rt].siz+=t[t[rt].l].siz;
		t[son].r=rt;
	}
	else{
		son=t[rt].r;
		t[son].siz=t[rt].siz;
		t[rt].siz-=t[t[rt].r].siz;
		t[rt].r=t[son].l;
		t[rt].siz+=t[t[rt].r].siz;
		t[son].l=rt;
	}
	rt=son;
}
inline void insert(int &rt,int x){
	if(!rt){
		rt=++cnt;t[rt].val=x;t[rt].pri=rand();
	}
	++t[rt].siz;
	if(t[rt].val>x) insert(t[rt].l,x);
	else if(t[rt].val<x) insert(t[rt].r,x);
	else return;
	if(t[rt].l&&t[rt].pri>t[t[rt].l].pri) rotate(rt,0);
	if(t[rt].r&&t[rt].pri>t[t[rt].r].pri) rotate(rt,1);
}
inline void remove(int &rt,int x){
	--t[rt].siz;
	if(t[rt].val>x) remove(t[rt].l,x);
	else if(t[rt].val<x) remove(t[rt].r,x);
}
inline int count(int rt,int x){
	if(!rt) return 1;
	if(t[rt].val>x) return count(t[rt].l,x);
	else if(t[rt].val<x) return t[rt].siz-t[t[rt].r].siz+count(t[rt].r,x);
	else return t[t[rt].l].siz+1;
}
inline int kth(int rt,int x){
	if(t[t[rt].l].siz>=x) return kth(t[rt].l,x);
	else if(t[rt].siz-t[t[rt].r].siz<x) return kth(t[rt].r,x-t[rt].siz+t[t[rt].r].siz);
	else return t[rt].val;
}
int main(){
	srand(time(NULL));
	int n,opt,x;
	read(n);
	for(register int i=1;i<=n;++i){
		read(opt);read(x);
		if(opt==1) insert(root,x);
		else if(opt==2) remove(root,x);
		else if(opt==3){
			put(count(root,x));putchar('\n');
		}
		else if(opt==4){
			put(kth(root,x));putchar('\n');
		}
		else if(opt==5){
			put(kth(root,count(root,x)-1));putchar('\n');
		}
		else{
			put(kth(root,count(root,x+1)));putchar('\n');
		}
	}
	return 0;
}