rt. 数据往下翻

#include<iostream>
using namespace std;
const int N = 114514+1919810,inf = 0x7f7f7f7f;

int m,n,x,opt,tot,root,last,ansxor;
struct node{
	int son[2],fa,cnt,data,sizee;
}tn[N];

void add_node(int x,int w){
	tn[x].data = w;
	tn[x].sizee = tn[x].cnt = 1;
}

void push_up(int x){
	tn[x].sizee = tn[tn[x].son[0]].sizee + tn[tn[x].son[1]].sizee + tn[x].cnt;
	return;
}

int find(int k){
	int x = root;
	while(tn[x].son[tn[x].data<k] && tn[x].data != k) x = tn[x].son[tn[x].data<k];
	return x;
}

void rotate(int x){
	int y = tn[x].fa,z = tn[y].fa,k = (tn[y].son[1] == x);
	tn[y].son[k] = tn[x].son[k^1];
	tn[tn[x].son[k^1]].fa = y;
	tn[x].son[k^1] = y;
	tn[y].fa = x;
	tn[z].son[tn[z].son[1] == y] = x;
	tn[x].fa = z;
	push_up(y);push_up(x);
}

void splay(int x,int k){
	while(tn[x].fa ^ k){
		int y = tn[x].fa,z = tn[y].fa;
		if(z^k) ((tn[y].son[1] == x) ^ (tn[z].son[1] == y)) ? rotate(x) : rotate(y);
		rotate(x);
	}
	if(!k) root = x;
}

int pre_nxt(int x,int k){
	splay(find(x),0);
	if(tn[root].data < x && !k) return root;
	if(tn[root].data > x && k) return root;
	int p = tn[root].son[k];
	while(tn[p].son[k^1]) p = tn[p].son[k^1];
	return p;
}

void ins(int k){
	int x = find(k);
	if(tn[x].data != k){
		tn[x].son[tn[x].data < k] = ++tot;
		add_node(tot,k);
		tn[tot].fa = x;
		splay(tot,0);
	}else ++tn[x].cnt,splay(x,0);
}

void del(int k){
	int x = pre_nxt(k,0),y = pre_nxt(k,1);
	splay(x,0);splay(y,x);
	if(tn[tn[y].son[0]].cnt > 1) --tn[tn[y].son[0]].cnt,splay(tn[y].son[0],0);
	else tn[y].son[0] = 0,splay(y,0);
}

int f_rank(int x){
	splay(find(x),0);
	if(tn[root].data < x){
		while(tn[root].son[1] && tn[tn[root].son[1]].data < x) splay(tn[root].son[1],0);
		return tn[tn[root].son[0]].sizee + 2;
	}
	return tn[tn[root].son[0]].sizee + 1;
}

int f_val(int p,int x){
	if(!p) return 1;
	int siz = tn[tn[p].son[0]].sizee;
	if(siz < x && x <= siz+tn[p].cnt) return tn[p].data;
	if(x <= siz) return f_val(tn[p].son[0],x);
	else return f_val(tn[p].son[1],x-siz-tn[p].cnt);
}

signed main(){
	ios::sync_with_stdio(0);cin.tie(0);
	cin >> m >> n;
	ins(-inf);ins(+inf);
	for(int i = 1;i <= m && cin >> x;++i) ins(x);
	for(int i = 1;i <= n;++i){
		cin >> opt >> x;x^= last;
		if(opt == 1) ins(x);
		else if(opt == 2) del(x);
		else if(opt == 3) ins(x),last = f_rank(x)-1,del(x);
		else if(opt == 4) last = f_val(root,x+1);
		else if(opt == 5) ins(x),last = tn[pre_nxt(x,0)].data,del(x);
		else if(opt == 6) ins(x),last = tn[pre_nxt(x,1)].data,del(x);
		if(3 <= opt && opt <= 6) ansxor ^= last;
	}
	cout << ansxor;
	return 0;
}