萌新 Splay TLE 求条

#include<bits/stdc++.h>
#define ll long long
#define ull unsigned long long
#define pii pair <int , int>
#define pb push_back
#define fi first
#define se second
#define fastio ios::sync_with_stdio(false) , cin.tie(0) , cout.tie(0);
using namespace std;
struct SPLAY
{
	static const int MAXN = 3e6 + 10 , INF = (1 << 30) + 1; //MAXN为平衡树的最大节点数
	int rtpos , id;
	int fa[MAXN] , son[MAXN][2];
	int sz[MAXN] , cnt[MAXN];
	int val[MAXN];
	SPLAY()
	{
		rtpos = id = 0;
		return;
	}
	/*
	rtpos为平衡树的根节点编号 
	id为平衡树当前的节点数
	cnt标记当前节点对应权值的出现次数 
	sz存储一个节点子树内的元素（而非节点）个数 
	*/

	inline bool dir(int pos) { return pos == son[fa[pos]][1]; }
	inline void pushup(int pos) { return sz[pos] = sz[son[pos][0]] + sz[son[pos][1]] + cnt[pos] , void(); }
	/*
	dir获取一个点为其父亲的左子树还是右子树
	pushup用于更新一个点的信息 
	*/

	inline int newnode(int kval , int fapos) //newnode用于新建一个节点
	{
		id++;
		val[id] = kval , cnt[id] = sz[id] = 1 , fa[id] = fapos;
		son[id][0] = son[id][1] = 0;
		return id;
	}

	void rotate(int pos) //rotate用于将一个点向上旋转（这里采用与Treap不同的实现方式是为了方便splay操作）
	{
		bool flag = dir(pos);
		int x = pos , y = fa[pos] , z = fa[fa[pos]];

		son[y][flag] = son[x][flag ^ 1];
		if(son[x][flag ^ 1]) fa[son[x][flag ^ 1]] = y;

		fa[x] = z;
		if(z) son[z][dir(y)] = x;

		son[x][flag ^ 1] = y;
		fa[y] = x;

		pushup(y);
		pushup(x);
		return;
	}
	
	void splay(int pos , int targ) //splay用于将一个点pos旋转到成为targ的儿子为止
	{
		while(fa[pos] != targ)
		{
			int x = pos , y = fa[pos];
			if(fa[y] != targ)
			{
				if(dir(x) == dir(y)) rotate(y);
				else rotate(x);
			}
			rotate(x);
		}
		if(!targ) rtpos = pos;
		return;
	}
	
	bool find_val(int &pos , int nowval) //find_val函数会在以pos为根的子树当中找到权值为nowval的节点并将其旋至该子树的根部并返回true，若无权值为nowval的节点，则会随机选择nowval的前驱/后继节点旋至该子树根部并返回false
	{
		int x = pos , y = fa[pos];
		while(x && val[x] != nowval)
		{
			y = x;
			x = son[x][nowval >= val[x]];
		}
		splay((x ? x : y) , fa[pos]);
		pos = (x ? x : y);
		return (x ? 1 : 0);
	}
	
	bool find_rk(int &pos , int nowrk) //find_rk函数会在以pos为根的子树当中找到包含其树内第nowrk个元素的节点，并将其旋至该子树的根部（若找不到这样的节点则会返回false）
	{
		int x = pos;
		if(sz[pos] < nowrk) return 0;
		while(true)
		{
			if(sz[son[x][0]] >= nowrk) x = son[x][0];
			else if(sz[son[x][0]] + cnt[x] >= nowrk) break;
			else
			{
				nowrk -= sz[son[x][0]] + cnt[x];
				x = son[x][1];
			} 
		}
		splay(x , fa[pos]);
		pos = x;
		return 1;
	}
	
	int merge(int x , int y) //merge函数会将以x为根和以y为根的两颗平衡树合并，并返回新树的根节点（注意：x树中的最大值必须严格小于y树中的最小值） 
	{
		if(!x || !y) return x | y;
		int now = y;
		while(son[now][0]) now = son[now][0];
		splay(now , 0);
		son[now][0] = x , fa[x] = now;
		pushup(now);
		return now;
	}
	
	void insert(int &pos , int lst , int nowval) //insert函数会向整棵平衡树中插入一个元素，并将其所在节点旋转至平衡树根部
	{
		if(!pos)
		{
			pos = newnode(nowval , lst);
			splay(pos , 0);
			return;
		}
		int now = pos;
		while(true)
		{
			if(val[now] == nowval)
			{
				cnt[now]++;
				pushup(now);
				splay(now , 0);
				return;
			}
			bool dir = nowval >= val[now];
			if(!son[now][dir])
			{
				int tmpnode = newnode(nowval , now);
				son[now][dir] = tmpnode;
				splay(tmpnode , 0);
				return;
			}
			now = son[now][dir];
		}
		return;
	}
	
	bool erase(int nowval) //erase函数会查找到包含权值为nowval的元素的节点并删除该节点中的一个元素，若存在这样的节点并成功删除则返回true，否则返回false 
	{
		bool res = find_val(rtpos , nowval);
		if(!res) return 0;
		if(val[rtpos] != nowval) return 0;
		cnt[rtpos]-- , sz[rtpos]--;
		if(!cnt[rtpos])
		{
			int x = son[rtpos][0] , y = son[rtpos][1];
			fa[x] = fa[y] = 0;
			rtpos = merge(x , y);
		}
		return 1;
	}
	
	int get_rk(int pos , int nowval) //get_rk会返回以pos为根节点的子树内第一个权值为nowval的元素的排名 
	{
		bool res = find_val(pos , nowval);
		if(!res) return -INF;
		return (son[pos][0] ? sz[son[pos][0]] : 0) + 1;
	}
	
	int get_val(int pos , int nowrk) //get_rk会返回以pos为根节点的子树内排名为nowval的元素的值
	{
		bool res = find_rk(pos , nowrk);
		if(!res) return -INF;
		return val[pos];
	}
	
	int getmax(int pos) //getmax会返回以pos为根节点的子树内的元素最大值 
	{
		int x = pos;
		while(son[x][1]) x = son[x][1];
		splay(x , 0);
		return val[x];
	}
	
	int getmin(int pos) //getmin会返回以pos为根节点的子树内的元素最小值 
	{
		int x = pos;
		while(son[x][0]) x = son[x][0];
		splay(x , 0);
		return val[x];
	}
	
	int get_prev(int pos , int nowval) //get_prev会返回pos为根节点的子树内nowval的前驱
	{
		find_val(pos , nowval);
		if(val[pos] >= nowval)
		{
			if(!son[pos][0]) return -INF; 
			return getmax(son[pos][0]);
		}
		return val[pos];
	}
	
	int get_nxt(int pos , int nowval) //get_nxt会返回pos为根节点的子树内nowval的后继
	{
		find_val(pos , nowval);
		if(val[pos] <= nowval)
		{
			if(!son[pos][1]) return -INF; 
			return getmin(son[pos][1]);
		}
		return val[pos];
	}
};
SPLAY T;
int n , q , lst , ans;
int main()
{
	fastio;
	cin >> n >> q;
	for(int i = 1 ; i <= n ; i++)
	{
		int tmp;
		cin >> tmp;
		T.insert(T.rtpos , 0 , tmp);
	}
	while(q--)
	{
		int op , x;
		cin >> op >> x;
		x ^= lst;
		if(op == 1) T.insert(T.rtpos , 0 , x);
		else if(op == 2) T.erase(x);
		else if(op == 3)
		{
			lst = max(T.get_rk(T.rtpos , T.get_prev(T.rtpos , x)) , 0) + 1;
			ans ^= lst;
		}
		else if(op == 4)
		{
			lst = T.get_val(T.rtpos , x);
			ans ^= lst;
		}
		else if(op == 5)
		{
			lst = T.get_prev(T.rtpos , x);
			ans ^= lst;
		}
		else if(op == 6)
		{
			lst = T.get_nxt(T.rtpos , x);
			ans ^= lst;
		}
	}
	cout << ans;
	return 0;
}