来自刚刚学会Treap的蒟蒻

题目链接：

• P6136 【模板】普通平衡树（数据加强版）
• 弱化版 P6136 【模板】普通平衡树

特别不习惯用一堆数组，结构体多香啊

struct node{
	int son[2];//son[
	int size,cnt;
	int val,rd;
}trp[1500000];
int tot,root;

其实完整代码里都有~
只不过无聊，单独拿出来~

int rrand(void){
    return seed=(int)((long long)(seed)*974485642LL%21474836LL);
    /*手写rand()取随机数*/
}

#include<bits/stdc++.h>
#define re register
#define rd(x) x=read()
struct node{
	int son[2];//son[0]左儿子，son[1]右儿子 
	int size,cnt;
	//因为treap不希望出现值相同的节点，（想想为什么） 
	//所以用cnt统计相同的值 
	int val,rd;
	//rd 是随机的权值，整个树按照这个打乱 
	//当然，rd也可以被称为该节点的优先级 
}trp[1500000];
int tot,root;
int seed=5201314;
int rrand(void){
    return seed=(int)((long long)(seed)*974485642LL%21474836LL);
    /*手写rand()取随机数*/
}

void newnode(int &now,int val){
	/* 
	val = val
	size = 1
	cnt = 1;
	rd rand()
	*/
	/*基础的新建节点，没毛病*/ 
	now = ++tot;
	trp[now].val = val;
	trp[now].size = trp[now].cnt = 1;
	trp[now].rd = rrand();
	/*这里吐槽下,treap真的是看脸的算法啊*/
}
void update(int now){
	/*更新新节点，很简单，这里没啥问题 */
	trp[now].size = trp[trp[now].son[0]].size+trp[trp[now].son[1]].size+trp[now].cnt;
}
void rotate(int &now,int d){
	/*
	自闭了十分钟的旋转操作，
	位运算理解成左右儿子切换或者左右方向切换就好。 
	*/
	int son = trp[now].son[d^1];
	trp[now].son[d^1] = trp[son].son[d];
	trp[son].son[d] = now;
	now = son;
	/*注意，从下到上更新，先更新旋转后节点的d儿子，最后更新旋转的now节点*/ 
	update(trp[now].son[d]);
	update(now);
}
void insert(int &now,int val){
	if(!now){
		newnode(now,val);//终于可以插入新节点了 
		return;
	}//在那之前，我们需要找到在何处插
	++trp[now].size;
	if(trp[now].val==val){
		trp[now].cnt++;//前面提到的计数器，相同的值直接统计数量就好
		update(now);//我还在思考这里要不要update一下 
		return;
	}
	if(trp[now].val>val){
		insert(trp[now].son[0],val);
		if(trp[now].rd<trp[trp[now].son[0]].rd)
			rotate(now,1);
	}//左右分头，记住一点，这棵树中，越往上rd越大，所以我们if比较里的内容其实很简单
	//如果遇到儿子的rd比父辈大的时候，我们就旋转一下 
	else{
		insert(trp[now].son[1],val);
		if(trp[now].rd<trp[trp[now].son[1]].rd)
			rotate(now,0);
	}
	update(now);
}
void del(int &now,int val){
	if(!now)return;//都没节点了，你删个锤子，可以加返回值判断是否删成功 
	++trp[now].size;
	if(trp[now].val==val){
		if(trp[now].cnt>1){
			trp[now].cnt--;
			update(now);
			return;
		}
		if(trp[now].son[0]||trp[now].son[1]){
			if(!trp[now].son[1]||trp[trp[now].son[0]].rd>trp[trp[now].son[1]].rd)
				rotate(now,1),del(trp[now].son[1],val);
			else
				rotate(now,0),del(trp[now].son[0],val);
		}//删除这段其实用手画三四张模拟就懂了 
		else now = 0;
	}//蒟蒻的我可能会在B站录个视频什么的 
	else if(trp[now].val>val) 
		del(trp[now].son[0],val);
	else del(trp[now].son[1],val);
	update(now);
}
int find_rank(int now,int val){
	if(!now)
		return INT_MIN;
	if(trp[now].val==val)
		return trp[trp[now].son[0]].size+1;
	else if(trp[now].val>val)
		return find_rank(trp[now].son[0],val);
	else
		return trp[trp[now].son[0]].size + trp[now].cnt + find_rank(trp[now].son[1],val);
}
int find_val(int now,int rank){
	if(!now)
		return INT_MAX;
	if(trp[trp[now].son[0]].size>=rank)
		return find_val(trp[now].son[0],rank);
	else if(trp[trp[now].son[0]].size+trp[now].cnt>=rank)
		return trp[now].val;
	else
		return find_val(trp[now].son[1],rank-trp[trp[now].son[0]].size-trp[now].cnt);
}
int find_pre(int val){
	re int now = root,pre = 0;
	while(now){
		if(trp[now].val<val)
			pre = trp[now].val,now = trp[now].son[1];
		else
			now = trp[now].son[0];
	}
	return pre;
}
int find_nex(int val){
	re int now = root,nex = 0;
	while(now){
		if(trp[now].val>val)
			nex = trp[now].val,now = trp[now].son[0];
		else
			now = trp[now].son[1];
	}
	return nex;
}
inline int read(){
	re int ans = 0;
	re bool f = 1;
	re char ch = getchar();
	while(ch<'0'||ch>'9')ch=='-'?f=0,ch=getchar():ch=getchar();
	while(ch>='0'&&ch<='9')ans =(ans<<3)+(ans<<1)+(ch^48),ch = getchar(); 
	return f?ans:-ans;
} 
signed main(void){
	int n,m,last = 0,ans = 0,ooo;
	n = read();m = read();++n;++m;
	while(--n){
		ooo = read();
		insert(root,ooo);
	}
	while(--m){
		int opt,x;
		opt = read();
		x = read();
		switch(opt){
			case 1:
				insert(root,x^last);
				break;
			case 2:
				del(root,x^last);
				break;
			case 3:
				ans ^= (last = find_rank(root,x^last));
				break;
			case 4:
				ans ^= (last = find_val(root,x^last));
				break;
			case 5:
				ans ^= (last = find_pre(x^last));
				break;
			case 6:
				ans ^= (last = find_nex(x^last));
				break;			
		}
	}
	printf("%d",ans);
	return 0;
}

感谢观看，如有不懂欢迎评论，博主全年365天无休，24小时内必回

嘿嘿，点个关注推荐呗~