>Link

luogu P3391

---

>Description

给你一个初始为 1 ~ n 的序列
不断对一些区间进行翻转操作
输出最终的序列

---

>解题思路

放放其他大佬的Splay讲解 orz
这里简单说一下Splay：
相对于treap，不用用随机数（大家都知道随机数这种东西就是看rp的嘛）；两者都是二叉查找树（好像是废话
然后旋转操作
设要选的点x，x的父亲y，x的祖父z
把x旋到y，直接旋上去
把x旋到z，这里考虑到维护平衡树的平衡，我们要分情况讨论：
x和y 分别是 y和z 的同一个方向的儿子 > > >> >> 先旋y，再旋x
x和y 分别是 y和z 的不同一个方向的儿子 > > >> >> 先旋x，再旋x（x旋两次上去）

这道题，要我们对一个区间进行翻转操作
我们先对原始的 1 ~ n 按顺序建一个平衡树，然后我们知道序列就是这棵平衡树的中序遍历
假设这个区间是 [ l , r ] [l,r] [l,r]
根据二叉查找树的性质，如果 l − 1 l-1 l−1在根节点， r + 1 r+1 r+1是根节点的右儿子，那 [ l , r ] [l,r] [l,r]区间所有的点就在根节点的右儿子的左儿子子树里了
那我们就把 l − 1 l-1 l−1旋到根节点，把 r + 1 r+1 r+1旋到根节点的右儿子那，对根节点的右儿子的左儿子子树进行翻转操作
对一整个子树进行翻转，且子树是二叉查找树，那我们就把这个子树中所有节点的左右儿子互换一下就行了
但是这样会T飞，所以这里我们用到线段树思想中的懒标记，把要翻转的子树的根标记一下，遇到的时候再操作和标记下传

---

>代码

#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
#define N 100010
using namespace std;

struct tree
{
	int son[5], lazy, val, f, siz;
} t[N];
int n, m, a[N], cnt, root;

void update (int x)
{t[x].siz = 1 + t[t[x].son[0]].siz + t[t[x].son[1]].siz;}
void pushdown (int x)
{
	if (!t[x].lazy) return;
	int ls = t[x].son[0], rs = t[x].son[1];
	t[ls].lazy ^= 1, t[rs].lazy ^= 1;
	swap (t[x].son[0], t[x].son[1]);
	t[x].lazy = 0;
}
void spin (int x)
{
	int y = t[x].f;
	int z = t[y].f;
	int k = (x == t[y].son[1]), kk = (y == t[z].son[1]);
	t[y].son[k] = t[x].son[k ^ 1], t[t[x].son[k ^ 1]].f = y;
	t[x].son[k ^ 1] = y, t[y].f = x;
	t[z].son[kk] = x, t[x].f = z;
	update (y);
	update (x);
//	update (z); z的子树大小没变
}
void splay (int x, int ff)
{
	if (!x) return;
	pushdown (x);
	while (t[x].f != ff)
	{
		int y = t[x].f;
		int z = t[y].f;
//		pushdown (x), pushdown (y), pushdown (z); splay时不要翻转区间!! (子树不变 
		if (z != ff)
		{
			if ((t[z].son[0] == y) == (t[y].son[0] == x)) spin (y);
			else spin (x);
		}
		spin (x);
	}
	if (!ff) root = x;
}
void insert (int x)
{
	int u = root, ff = 0;
	while (u)
	{
		ff = u;
		u = t[u].son[x > t[u].val];
	}
	u = ++cnt;
	t[u].val = x;
	t[u].siz = 1;
	t[u].lazy = 0;
	if (ff)
	{
		t[u].f = ff;
		t[ff].son[x > t[ff].val] = u;
	}
	else root = u;
	splay (u, 0);
}
int find (int x) //找第x个
{
	if (!x) return 0;
	int u = root, ls, rs;
	while (x)
	{
		pushdown (u);
		ls = t[u].son[0], rs = t[u].son[1];
		if (t[ls].siz >= x) u = ls;
		else if (t[ls].siz + 1 == x) x = 0;
		else x -= t[ls].siz + 1, u = rs;
	}
	return u;
}
void dfs (int u)
{
	if (!u) return;
	pushdown (u); 
	int ls = t[u].son[0], rs = t[u].son[1];
	dfs (ls);
	if (t[u].val - 1 <= n && t[u].val - 1 >= 1)
	  printf ("%d ", t[u].val - 1);
	dfs (rs);
}

int main()
{
	scanf ("%d%d", &n, &m);
	for (int i = 1; i <= n + 2; i++) //平衡树中的常规操作，放另外两个小值和大值进去，防止越界
	  insert (i); //这里放进去的i实际表示i-1（因为0很特殊不好操作
	int l, r, x;
	for (int i = 1; i <= m; i++)
	{
		scanf ("%d%d", &l, &r);
		x = find (l);
		splay (x, 0);
		x = find (r + 2);
		splay (x, root);
		t[t[t[root].son[1]].son[0]].lazy ^= 1;
	}
	dfs (root);
	return 0;
}