记录详情

很玄学，下载了 #2 发现和标准输出没有出入结果还是 WA 了不知道为什么

//【模板】FHQ 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,pri,siz;
}t[MAXN];
int root,cnt;
inline void puts(int rt){
	int s1,s2,t1[MAXN],t2[MAXN];
	bool f;
	s1=1;t1[1]=rt;
	while(true){
		f=false;s2=0;
		for(register int i=1;i<=s1;++i){
			put(t[t1[i]].val);putchar(' ');
		}
		putchar('\n');
		for(register int i=1;i<=s1;++i){
			if(t[t1[i]].l||t[t1[i]].r) f=true;
			++s2;t2[s2]=t[t1[i]].l;++s2;t2[s2]=t[t1[i]].r;
		}
		if(!f) break;
		s1=s2;
		for(register int i=1;i<=s1;++i) t1[i]=t2[i];
	}
	putchar('\n');
}
inline void split(int rt,int x,int &l,int &r){
	if(!rt){
		l=r=0;return;
	}
	if(t[rt].val>=x){
		r=rt;t[rt].siz-=t[t[rt].l].siz;
		split(t[rt].l,x,l,t[rt].l);t[rt].siz+=t[t[rt].l].siz;
	}
	else{
		l=rt;t[rt].siz-=t[t[rt].r].siz;
		split(t[rt].r,x,t[rt].r,r);t[rt].siz+=t[t[rt].r].siz;
	}
}
inline int merge(int l,int r){
	if(!l||!r) return l+r;
	if(t[l].pri<t[r].pri){
		t[l].r=merge(t[l].r,r);
		t[l].siz+=t[r].siz;
		return l;
	}
	else{
		t[r].l=merge(l,t[r].l);
		t[r].siz+=t[l].siz;
		return r;
	}
}
inline void insert(int x){
	int l,r,m;
	split(root,x,l,r);
	++cnt;
	t[cnt].l=t[cnt].r=0;t[cnt].val=x;t[cnt].pri=rand();t[cnt].siz=1;
	root=merge(merge(l,cnt),r);
}
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);
	else if(t[rt].siz==t[t[rt].l].siz+t[t[rt].r].siz){
		int l,r,m;
		split(root,x,l,r);
		split(l,x-1,l,m);
		root=merge(l,r);
	}
}
inline int count(int x){
	int l,r,ans;
	split(root,x-1,l,r);
	ans=t[l].siz+1;
	merge(l,r);
	return ans;
}
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(){
	freopen("P3369_2.in","r",stdin);
	freopen("P3369_2.ans","w",stdout);
	int n,opt,x;
	read(n);
	for(register int i=1;i<=n;++i){
		read(opt);read(x);
		if(opt==1) insert(x);
		else if(opt==2) remove(root,x);
		else if(opt==3){
			put(count(x));putchar('\n');
		}
		else if(opt==4){
			put(kth(root,x));putchar('\n');
		}
		else if(opt==5){
			put(kth(root,count(x)-1));putchar('\n');
		}
		else if(opt==6){
			put(kth(root,count(x+1)));putchar('\n');
		}
	}
	return 0;
}