WBLT 96ptsMLE 求调

#include<bits/stdc++.h>
using namespace std;
template<typename T>
struct WBLT{
	private:
		double alpha=0.25;
		struct node{T v;int s;node*l,*r;}*root;
		bool leaf(node*p){return!p->l&&!p->r;}
		int size(node*p){return p?p->s:0;}
		void update(node*p){
			if(leaf(p))p->s=1;
			else p->s=size(p->l)+size(p->r),p->v=p->r->v;
		}node*merge(node*l,node*r){
			node*p=new node{0,0,l,r};
			update(p);return p;
		}void rotate(node*&p,bool d){
			if(!d){
				p->r=merge(p->l->r,p->r);
				p->l=p->l->l;
			}else{
				p->l=merge(p->l,p->r->l);
				p->r=p->r->r;
			}
		}void maintain(node*&p){
			if(leaf(p))return;
			if(size(p->l)*alpha>size(p->r))rotate(p,0);
			else if(size(p->r)*alpha>size(p->l))rotate(p,1);
			if(size(p->l)*alpha>size(p->r))rotate(p->l,1),rotate(p,0);
			else if(size(p->r)*alpha>size(p->l))rotate(p->r,0),rotate(p,1);
		}inline void insert(node*&p,T v){
			if(leaf(p)){
				p->l=new node{min(v,p->v),1,0,0};
				p->r=new node{max(v,p->v),1,0,0};
			}else if(p->l->v>=v)insert(p->l,v);
			else insert(p->r,v);
			update(p);maintain(p);
		}inline void erase(node*&p,T v){
			if(p->l->v>=v){
				if(leaf(p->l)){
					node*t=p;delete p->l;
					p=p->r;delete t;return;
				}else erase(p->l,v);
			}else{
				if(leaf(p->r)){
					node*t=p;delete p->r;
					p=p->l;delete t;return;
				}else erase(p->r,v);
			}update(p);maintain(p);
		}
	public:
		WBLT():root(new node{INT_MAX,1,0,0}){}
		void insert(T v){insert(root,v);}
		void erase(T v){erase(root,v);}
		int order_of_key(T v){
			node*p=root;int ans=0;
			while(p){
				if(leaf(p))return ans+1;
				else if(p->l->v>=v)p=p->l;
				else ans+=size(p->l),p=p->r;
			}return 1;
		}T find_by_order(int k){
			node*p=root;
			while(p){
				if(leaf(p))return k==1?p->v:T();
				else if(size(p->l)>=k)p=p->l;
				else k-=size(p->l),p=p->r;
			}return T();
		}T pre(T v){return find_by_order(order_of_key(v)-1);}
		T suc(T v){return find_by_order(order_of_key(v+1));}
};WBLT<int>tr;int n,m,lst,t,x,ans;
int main(){
	ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);
	cin>>n>>m;
	for(int i=1;i<=n;i++)cin>>x,tr.insert(x);
	while(m--){
		cin>>t>>x;x^=lst;
		if(t==1)tr.insert(x);
		else if(t==2)tr.erase(x);
		else if(t==3)lst=tr.order_of_key(x),ans^=lst;
		else if(t==4)lst=tr.find_by_order(x),ans^=lst;
		else if(t==5)lst=tr.pre(x),ans^=lst;
		else if(t==6)lst=tr.suc(x),ans^=lst;
	}cout<<ans;
}