萌新的splay求职

#include<bits/stdc++.h>
#define rep(i,j,k) for(register int i(j);i<=k;++i)
using namespace std;
const int N = 100079;
const int inf = 0x7fffffff;
int n, m;
int a[N];
#define lc son[x][0]
#define rc son[x][1]
struct BST
{
	int tot, size[N], son[N][2];
	int fa[N], rev[N],val[N];
	int root;
	inline void pushup(int x)
	{
		size[x] = size[lc] + size[rc] + 1;
	}
	inline int relation(int x)
	{
		return son[fa[x]][1] == x;
	}
	inline void pushdown(int x)
	{
		if(!rev[x]) return ;
		rev[lc] ^= 1;
		rev[rc] ^ 1;
		swap(fa[lc],fa[rc]);
		swap(size[lc],size[rc]);
		swap(val[lc],val[rc]);
		swap(rev[lc],rev[rc]);
		swap(son[1][lc],son[1][rc]);
		swap(son[0][lc],son[0][rc]);
		rev[x] = 0;
	}
	
	inline void connect(int x, int f, int next)
	{
		fa[x] = f;
		son[f][next] = x;
	}
	inline void rotate(int x)
	{
		int y(fa[x]), r = fa[y];
		pushdown(y);pushdown(r);
		int dy = relation(y), dx = relation(x);
		int b = son[x][dx ^ 1];
   
		connect(b, y, dx);
		connect(y, x, dx ^ 1);
		connect(x, r, dy);
		pushup(y);
		pushup(x);
	}
	inline void splay(int x, int to)
	{
		int ed = fa[to];
		while(fa[x] != ed)
		{
			int y = fa[x];
			if(fa[y] == ed) rotate(x);
			else if(relation(x) == relation(y)) rotate(y), rotate(x);
			else rotate(x), rotate(x);
		}
	}
	inline int create(int key, int f)
	{
		tot++;
		val[tot]=key;
		size[tot] = 1;
		son[tot][0] = son[tot][1] = 0;
		fa[tot] = f;
		return tot;
	}
	inline int build(int L, int R, int f)
	{
		if(L > R) return 0;
		int mid((L + R) >> 1);
		int p = create(a[mid], f);
		son[p][0] = build(L, mid - 1, p);
		son[p][1] = build(mid + 1, R, p);
		pushup(mid);
		return p;
	}
	inline int findkey(int x, int k)
	{	
		pushdown(x);
		if(size[lc] + 1 == k) return x;
		if(k < size[lc] + 1) return findkey(lc, k);
		if(k > size[lc] + 1) return findkey(rc, k - 1 - size[lc]);
	}
	inline void rever(int x, int y)
	{
		int L=x-1,R=y+1;
		L=findkey(root,L),R=findkey(root,R);
		splay(L, root);
		splay(R, son[root][1]);
		R=son[root][1];
		rev[son[R][0]] ^= 1;
	}
	inline void print(int x)
	{
		pushdown(x);
		if(lc) print(lc);
		if(val[x]!=inf&&val[x]!=-inf) cout << val[x] << ' ';
		if(rc) print(rc);
	}
} S;
int main()
{
	cin >> n >> m;
	a[1] = -inf;
	a[n + 2] = inf;
	rep(i, 1, n) a[i + 1] = i;
	S.root=S.build(1, n + 2, 0);
	rep(i, 1, m)
	{
		int l, r;
		cin >> l >> r;
		S.rever(l + 1, r + 1);
	}
	S.print(S.root);
	return 0;
}