fhq-Treap 输出随机求调

样例过了。

#include <bits/stdc++.h>

using namespace std;

const int kMaxT = 1e5 + 5, kInf = 1e9;

int n, m, L, R, rt, tot, w[kMaxT], r[kMaxT], lc[kMaxT], rc[kMaxT], s[kMaxT];
bool t[kMaxT];

void PushUp(int u) { s[u] = s[lc[u]] + s[rc[u]] + 1; }

void PushDown(int u) {
  if (t[u]) {
    swap(lc[u], rc[u]), t[u] = 0;
    lc[u] && (t[lc[u]] ^= 1);
    rc[u] && (t[rc[u]] ^= 1);
  }
}

void Split(int u, int val, int &x, int &y) {
  if (!u) {
    return (x = y = 0, (void)0);
  }
  int rnk = s[lc[u]] + 1;
  PushDown(u);
  if (rnk <= val) {
    x = u, Split(rc[u], val - rnk, rc[u], y);
  } else {
    y = u, Split(lc[u], val, x, lc[u]);
  }
  PushUp(u);
}

int Merge(int x, int y) {
  if (!x || !y) {
    return x | y;
  } else if (r[x] <= r[y]) {
    PushDown(x);
    rc[x] = Merge(rc[x], y);
    return (PushUp(x), x);
  } else {
    PushDown(y);
    lc[y] = Merge(x, lc[y]);
    return (PushUp(y), y);
  }
}

void Ins(int x) {
  w[++tot] = x, s[tot] = 1, r[tot] = rand();
  rt = Merge(rt, tot);
}

void Print(int u) {
  if (u) {
    PushDown(u);
    Print(lc[u]);
    cout << w[u] << ' ';
    Print(rc[u]);
  }
}

int main() {
  // freopen("in.txt", "r", stdin);
  // freopen("out.txt", "w", stdout);
  srand(time(0));
  cin.tie(0)->sync_with_stdio(0);
  cin >> n >> m;
  for (int i = 1; i <= n; i++) {
    Ins(i);
  }
  for (int x, y, z; m--; x = y = z = 0) {
    cin >> L >> R;
    Split(rt, L - 1, x, y);
    Split(y, R - L + 1, y, z);
    t[y] ^= 1;
    rt = Merge(x, Merge(y, z));
  }
  Print(rt);
  return 0;
}