Splay-526互联

#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cstring>
#include<cmath>

using namespace std;

int n, m, res, last;
int root, chi[5211314][2], fat[5211314];
//root根节点 chi子节点(0左 1右) fat父节点 
int val[5211314], size[5211314], cnt[5211314], tot;
//val权值 size子树大小 cnt这个权值出现次数 tot平衡树节点个数 

struct SPLAY {
	void mintain( int now );//维护此节点的子树大小
	bool get( int now );//找是左儿子还是右儿子 返回false是左儿子 返回true是右儿子
	void clear( int now );//销毁这个节点
	void rotate( int x );//旋转
	void splay( int x );//伸展(即把x旋转到根节点)
	void insert( int x );//插入 数字x
	int find_rank( int now );//查询now的排名
	int find_num( int v );//查询排名为v的数
	int pre();//查询now的前驱
	int next();//查询now的后继
	void del( int now );//删除now 
}Splay;

inline int read() {
	int x = 0, f = 1;
	char ch = getchar();
	while ( ch < '0' || ch > '9' ) {
		if ( ch == '-' ) f *= -1;
		ch = getchar();
	}
	while ( ch >= '0' && ch <= '9' ) {
		x = ( x << 1 ) + ( x << 3 ) + ( ch - '0' );
		ch = getchar();
	}
	return x * f;
}

void SPLAY::mintain( int now ) {
	size[now] = size[chi[now][0]] + size[chi[now][1]] + cnt[now];
	return;
}

bool SPLAY::get( int now ) {
	if ( now == chi[fat[now]][0] ) {
		return false;
	}
	else {
		return true;
	}
}

void SPLAY::clear( int now ) {
	fat[now] = 0;
	chi[now][0] = 0;
	chi[now][1] = 0;
	val[now] = 0;
	size[now] = 0;
	cnt[now] = 0;
	return;
}

void SPLAY::rotate( int x ) {
	int y = fat[x], z = fat[y], chk = get(x);
	chi[y][chk] = chi[x][chk ^ 1];
	if ( chi[x][chk ^ 1] != 0 ) {
		fat[chi[x][chk ^ 1]] = y;
	}
	chi[x][chk ^ 1] = y;
	fat[x] = z;
	fat[y] = x;
	if ( z != 0 ) {
		chi[z][y == chi[z][1]] = x;
	}
	mintain( y );
	mintain( x );
	return;
}
	
void SPLAY::splay( int x ) {
	for (int i = fat[x]; i = fat[x], i != 0; rotate(x)) {
		if ( fat[i] != 0 ) {
			if ( get(x) == get(i) ) {
				rotate( i );
			}
			else {
				rotate( x );
			}
		}
	}
	root = x;
	return;
}
	
int SPLAY::find_rank( int now ) {
	int ans = 0, temp = root;
	while ( 1 ) {
		if ( temp == 0 ) {
			return ans + 1;
		}
		if ( now < val[temp] ) {
			temp = chi[temp][0];
		}
		else {
			ans += size[chi[temp][0]];
			if ( now == val[temp] ) {
				splay( temp );
				return ans + 1;
			}
			ans += cnt[temp];
			temp = chi[temp][1];
		}
	}
}	

void SPLAY::insert( int v ) {
	if ( root == 0 ) {
		tot ++;
		val[tot] = v;
		cnt[tot] ++;
		root = tot;
		mintain( root );
		return;
	}
	int temp = root, tem = 0;
	while ( 1 ) {
		if ( val[temp] == v ) {
			cnt[temp] ++;
			mintain( temp );
			mintain( tem );
			splay( temp );
			break;
		}
		tem = temp;
		temp = chi[temp][val[temp] < v];
		if ( temp == 0 ) {
			tot ++;
			val[tot] = v;
			cnt[tot] ++;
			fat[tot] = tem;
			chi[tem][val[tem] < v] = tot;
			mintain( tot );
			mintain( tem );
			splay( tot );
			break;
		} 
	}
	return;
}

int SPLAY::find_num( int v ) {
	
	int temp = root;
	while ( 1 ) {
		if ( chi[temp][0] != 0 && v <= size[chi[temp][0]] ) {
			temp = chi[temp][0];
		}
		else {
			v -= cnt[temp] + size[chi[temp][0]];
			if ( v <= 0 ) {
				
				splay( temp );
				return val[temp];
			}
			temp = chi[temp][1];
		}
	}
}

int SPLAY::pre() {
	int temp = chi[root][0];
	while ( chi[temp][1] ) {
		temp = chi[temp][1];
	}
	splay( temp );
	return temp;
}

int SPLAY::next() {
	int temp = chi[root][1];
	while ( chi[temp][0] ) {
		temp = chi[temp][0];
	}
	splay( temp );
	return temp;
}

void SPLAY::del( int now ) {
	find_rank(now);
	if ( cnt[root] > 1 ) {
		cnt[root] --;
		mintain(root);
		return;
	}
	if ( chi[root][0] == 0 && chi[root][1] == 0 ) {
		clear( root );
		root = 0;
		return;
	}
	if ( chi[root][0] == 0 ) {
		int temp = root;
		root = chi[root][1];
		fat[root] = 0;
		clear(temp);
		return;
	}
	if ( chi[root][1] == 0 ) {
		int temp = root;
		root = chi[root][0];
		fat[root] = 0;
		clear(temp);
		return;
	}
	int temp = root;
	int x = pre();
	fat[chi[temp][1]] = x;
	chi[x][1] = chi[temp][1];
	clear(temp);
	mintain(root);
	return;
}

int main() {
	n = read();
	m = read();
	for ( int i = 1, a; i <= n; ++ i) {
		a = read();
		Splay.insert(a);
	}
	for(int i = 1,opt,x;i <= m; i++)
	{
		scanf("%d%d",&opt,&x);
		x ^= last;
		if( opt == 1 ) {
			Splay.insert(x);
		}
		else if( opt == 2 ) {
			Splay.del(x);	
		}
		else if( opt == 3 )
		{
			last = Splay.find_rank(x);
			res ^= last;
		}
		else if( opt == 4 )
		{
			last = Splay.find_num(x);
			res ^= last;
		}
		else if( opt == 5 )
		{
			Splay.insert(x);
			last = val[Splay.pre()];
			res ^= last;
			Splay.del(x);
		}
		else
		{
			Splay.insert(x);
			last = val[Splay.next()];
			res ^= last;
			Splay.del(x);
		}
	}
	printf("%d",res);
	return 0;
}