splay回忆提纲

在二叉树上操作。splay(x, pa)这个函数把x旋转成pa的儿子，且这棵树和原来等价（旋转是可以等价旋转的）。

splay()内用到rotate(x)函数，rotate(x)就是等价地把x往上转一层。splay中对rotate有关照：假称x的父亲是y，y的父亲是z，则对于x，y，z连接方向不同的情况进行不同处理，写起来还是很简单明了的。

文艺平衡树 区间反转

前后插入0和n+1，旋转l，r时，把rank（注意是加入0后的rank不是原排名）l提到root，把rank r+2提到root的右儿子，然后给root的右儿子的左儿子上反转标记。

文艺平衡树代码

注意！insert中必须有splay(x, 0)，以更新初始root信息、维持平衡。

会出现y和z都是0的情况，但是记牢这么写没问题就行。

#include <bits/stdc++.h>
using namespace std;

int n, m, rt;
struct Node {
  int val;
  int fa;
  int ch[2];
  int siz;
  int tag;
  void init(int xval, int xfa) {
    val = xval;
    fa = xfa;
    ch[0] = ch[1] = 0;
    siz = 1;
    tag = 0;
  }
} node[100010]; int cnt = 0;

void pushdown(int x) {
  if (node[x].tag) {
    node[node[x].ch[0]].tag ^= 1;
    node[node[x].ch[1]].tag ^= 1;
    swap(node[x].ch[0], node[x].ch[1]);
    node[x].tag = 0;
  }
}

void update(int x) {
  node[x].siz = node[node[x].ch[0]].siz + node[node[x].ch[1]].siz + 1;
}

void rotate(int x) {
  int y = node[x].fa, z = node[y].fa;
  int xid = node[y].ch[1] == x, yid = node[z].ch[1] == y;
  node[z].ch[yid] = x;
  node[x].fa = z;
  node[y].ch[xid] = node[x].ch[xid ^ 1];
  node[node[x].ch[xid ^ 1]].fa = y;
  node[x].ch[xid ^ 1] = y;
  node[y].fa = x;
  update(x), update(y);
}

void splay(int x, int pa) { // let x be a son of pa
  while (node[x].fa != pa) {
    int y = node[x].fa, z = node[y].fa;
    if (z != pa) 
      (y == node[z].ch[1]) == (x == node[y].ch[1]) ? rotate(y) : rotate(x);
    rotate(x);
  }
  if (pa == 0)
    rt = x;
}

void insert(int val) {
  int p = rt, fa = 0;
  while (p)
    fa = p, p = node[p].ch[val > node[p].val];
  int x = ++cnt;
  if (fa != 0)
    node[fa].ch[val > node[fa].val] = x;
  node[x].init(val, fa);
  splay(x, 0); // i dont know why
}

int findk(int k) {
  int x = rt;
  while (1) {
    pushdown(x);
    if (k == node[node[x].ch[0]].siz + 1) break;
    if (k <= node[node[x].ch[0]].siz) x = node[x].ch[0];
    else k -= node[node[x].ch[0]].siz + 1, x = node[x].ch[1];
  }
  return x;
}

void print(int x) {
  if (x == 0) return;
  pushdown(x);
  print(node[x].ch[0]);
  if (1 <= node[x].val and node[x].val <= n)
    printf("%d ", node[x].val);
  print(node[x].ch[1]);
}

int main() {
  scanf("%d %d", &n, &m);
  for (int i = 0; i <= n + 1; ++i)
    insert(i);
  while (m--) {
    int l, r; scanf("%d %d", &l, &r);
    l = findk(l);
    // it's actually node l - 1
    r = findk(r + 2); 
    // cuz there is 0 in the tree
    splay(l, 0);
    splay(r, l);
    node[node[node[rt].ch[1]].ch[0]].tag ^= 1;
    // yep
  }
  print(rt);
  return 0;
}