传送门

看了一圈，好像真的没什么用指针的呢。。

明明觉得指针很好看（什么？？你说RE？？？听不见听不见）

其实我觉得用数组的话不RE直接WA调起来不是更困难嘛，毕竟通过gdb还可以知道哪里RE，WA就不知道咋回事了，是不是很有道理，虽然我还是调了几小时

我写的是fhq treap，核心是split和merge操作，思想高赞dalao都讲得很清楚，我语文弱渣就不班门弄斧了，主要是想提供一个指针版的参考吧QAQ

我真的是一整天都在搞分裂(split)，有种要进入七月枪毙名单的赶脚，慌张.jpg

#include<bits/stdc++.h>

#define LL long long

#define fr(i,x,y) for(int i=(x);i<=(y);i++)

#define rf(i,x,y) for(int i=(x);i>=(y);i--)

#define frl(i,x,y) for(int i=(x);i<(y);i++)

using namespace std;

const int N=100005;

struct node{

	int v,rnd,s,sz;  //s表示权值为v的个数,sz表示子树size,然而我经常忘记s的存在,直接写成1,挂了好久

	node* ch[2];

	inline int cmp(int x){ return x>v; } //这其实是写旋转treap时留下的历史遗留问题= =无视吧

	inline void maintain(){

		sz=s;

		if (ch[0]!=NULL) sz+=ch[0]->sz; //写指针一定要特别注意对NULL的判断

		if (ch[1]!=NULL) sz+=ch[1]->sz;

	}

	node(){

		ch[0]=ch[1]=NULL;

		rnd=rand();

	}

}nd[N];

int tot;

node* rt;

int n;

void read(int &x){ //读优一开始忘记负数了= =

	char ch=getchar();x=0;int w=0;

	for(;ch<'0'||ch>'9';ch=getchar()) if (ch=='-') w=1;

	for(;ch>='0'&&ch<='9';ch=getchar()) x=(x<<3)+(x<<1)+ch-'0';

	if (w) x=-x;

}

inline int sss(node* &o){

	return o==NULL?0:o->sz;

}

node* &kth(node* &o,int k){

	assert(o!=NULL);

	int s=sss(o->ch[0]);

	if (s+1<=k&&s+o->s>=k) return o;

	if (s+1>k) return kth(o->ch[0],k);

	return kth(o->ch[1],k-o->s-s);

}

void split(node* o,node* &L,node* &r,int k){ //split <=k

	if (o==NULL) return L=r=NULL,void();

	if (o->v<=k){

		split(o->ch[1],o->ch[1],r,k);

		L=o;

	} else{

		split(o->ch[0],L,o->ch[0],k);

		r=o;

	}

	o->maintain(); //要经常维护一下信息

}

node* &merge(node* &L,node* &r){

	if (L==NULL) return r;

	if (r==NULL) return L;

	if (L->rnd<r->rnd){

		L->ch[1]=merge(L->ch[1],r);

		L->maintain();

		return L;

	} else{

		r->ch[0]=merge(L,r->ch[0]);

		r->maintain();

		return r;

	}

}

void add_node(int v){

	node* L;

	node* r;node* xx;

	split(rt,L,r,v);

	if (L!=NULL&&(xx=kth(L,L->sz))->v==v){ //如果存在这个数直接加个数

		split(L,L,xx,v-1);

		xx->s++;xx->sz++;  //不要忘记加size

		//rt=merge(L,r);

	}else{

		xx=&nd[++tot];

		xx->s=xx->sz=1;xx->v=v;

	}

	rt=merge(merge(L,xx),r);

}

void del_node(int v){

	node *L,*r,*mid;

	split(rt,L,r,v-1);

	split(r,mid,r,v);

	if (mid!=NULL&&mid->s>1) mid->s--,mid->sz--,r=merge(mid,r);

	rt=merge(L,r);

}

int rk(node* &o,int v){

	assert(o!=NULL);

	if (o->v==v) return sss(o->ch[0])+1;

	if (v<o->v) return rk(o->ch[0],v);

	 else return rk(o->ch[1],v)+sss(o->ch[0])+o->s;

}

int rkk(node* rt,int v){

	node *L,*r;

	split(rt,L,r,v-1);

	int ans=sss(L)+1;

	rt=merge(L,r);

	return ans;

}

//rk和rkk都可以求rank,一个通过split一个通过size,好像rkk更快?感觉有点奇怪...

int main(){

	srand(19260817);

	read(n);

	int tp,x;

	node *L,*r;

	int s=0;

	add_node(19260817);

	fr(o,1,n){

		read(tp);read(x);

		if (tp==1) add_node(x);

		if (tp==2) del_node(x);

		if (tp==3) printf("%d\n",rk(rt,x)),s++;

		if (tp==4) printf("%d\n",kth(rt,x)->v),s++;

		if (tp==5){

			split(rt,L,r,x-1);

			printf("%d\n",kth(L,L->sz)->v),s++;

			rt=merge(L,r);

		}

		if (tp==6){

			split(rt,L,r,x);

			printf("%d\n",kth(r,1)->v),s++;

			rt=merge(L,r);

		}

		//if (s==670) printf("----%d %d %d\n",o,tp,x);

	}

	return 0;

}