文艺平衡树

  1 #include <bits/stdc++.h>
  2 #define L(x) e[x].son[0]
  3 #define R(x) e[x].son[1]
  4 using namespace std;
  5 const int N = 1e6 + 7;
  6 const int inf = 0x3f3f3f3f;
  7 int n, m, x, y;
  8 struct node{
  9     int son[2];
 10     int father, siz, val, rev;
 11 }e[N];
 12 int a[N], root, cnt;
 13 int identify(int x) {
 14     return e[e[x].father].son[0] == x ? 0 : 1;
 15 }
 16 void connect(int x, int fa, int Son) {
 17     e[x].father = fa;
 18     e[fa].son[Son] = x;
 19 }
 20 void update(int x) {
 21     e[x].siz = e[L(x)].siz + e[R(x)].siz + 1;
 22 }
 23 void pushdown(int x) {
 24     if (x && e[x].rev) {
 25         e[L(x)].rev ^= 1;
 26         e[R(x)].rev ^= 1;
 27         swap(L(x), R(x));
 28         e[x].rev = 0;
 29     }
 30 }
 31 void rotate(int x) {
 32     int fa = e[x].father, fason = identify(x);
 33     int gfa = e[fa].father, gfason = identify(fa);
 34     int B = e[x].son[fason ^ 1];
 35     connect(B, fa, fason), connect(fa, x, fason ^ 1);
 36     connect(x, gfa, gfason);
 37     update(fa), update(x);
 38 }
 39 void splay(int now, int to) {
 40     int tofa = e[to].father;
 41     while (e[now].father != tofa) {
 42         int fa = e[now].father, gfa = e[fa].father;
 43         if (gfa != tofa) {
 44             rotate(identify(now) == identify(fa) ? fa : now);
 45         }
 46         rotate(now);
 47     }
 48     if (to == root) root = now;
 49 }
 50 int build(int l, int r, int fa) {
 51     if (l > r) {
 52         return 0;
 53     }
 54     int mid = (l + r) / 2;
 55     int now = ++cnt;
 56     e[now].father = fa;
 57     L(now) = R(now) = 0;
 58     e[now].val = a[mid];
 59     e[now].siz++;
 60     L(now) = build(l, mid - 1, now);
 61     R(now) = build(mid + 1, r, now);
 62     update(now);
 63     return now;
 64 }
 65 int kth(int x) {
 66     int now = root;
 67     while (true) {
 68         pushdown(now);
 69         if (x <= e[L(now)].siz) {
 70             now = L(now);
 71         } else {
 72             x -= e[L(now)].siz + 1;
 73             if (!x) return now;
 74             now = R(now);
 75         }
 76     }
 77 }
 78 void reverse(int x, int y) {
 79     int l = x - 1, r = y + 1;
 80     l = kth(l), r = kth(r);
 81     splay(l, root), splay(r, R(l));
 82     int now = R(root);
 83     now = L(now);
 84     e[now].rev ^= 1;
 85 }
 86 void dfs(int now) {
 87     pushdown(now);
 88     if (L(now)) dfs(L(now));
 89     if (e[now].val != -inf && e[now].val != inf) {
 90         printf("%d ", e[now].val);
 91     }
 92     if (R(now)) dfs(R(now));
 93 }
 94 int main() {
 95     scanf("%d%d", &n, &m);
 96     a[1] = -inf;
 97     a[n + 2] = inf;
 98     for (int i = 1; i <= n; i++) {
 99         a[i + 1] = i;
100     }
101     root = build(1, n + 2, 0);
102     for (int i = 1; i <= m; i++) {
103         scanf("%d%d", &x, &y);
104         reverse(x + 1, y + 1);
105     }
106     dfs(root);
107     return 0;
108 }