【模板】WBLT

todo：可持久化

#include <bits/stdc++.h>
using namespace std;
#ifdef LOCAL
#define debug(...) fprintf(stderr, ##__VA_ARGS__)
#else
#define debug(...) void(0)
#endif
typedef long long LL;
template <int N>
struct WBLT {
  static constexpr double alpha = 0.292;
  int ch[N << 1][2], val[N << 1], siz[N << 1], tot, root, tsh[N << 1], tct;
  WBLT() { root = newnode(-1e9); }
  bool isleaf(int p) { return !ch[p][0]; }
  void destroy(int p) { tsh[++tct] = p; }
  void maintain(int p) {  // also known as: pushup
    if (isleaf(p)) return ;
    val[p] = val[ch[p][1]];
    siz[p] = siz[ch[p][0]] + siz[ch[p][1]];
  }
  bool rev[N << 1];
  void spread(int p) {
    rev[p] ^= 1;
  }
  void pushdown(int p) {
    if (!rev[p] || isleaf(p)) return ;
    spread(ch[p][0]), spread(ch[p][1]);
    swap(ch[p][0], ch[p][1]);
    rev[p] = false;
  }
  void rotate(int p, int r) {
    if (isleaf(p) || isleaf(ch[p][r])) return ;
    int q = ch[p][r];
    pushdown(q);
    swap(ch[p][0], ch[p][1]);
    swap(ch[p][r], ch[q][r]);
    swap(ch[q][0], ch[q][1]);
    maintain(q);
    maintain(p);
  }
  void update(int p) {  // also known as: maintain
    if (isleaf(p)) return ;
    pushdown(p);
    int r = siz[ch[p][0]] < siz[ch[p][1]];
    if (siz[ch[p][!r]] >= siz[p] * alpha) return;
    pushdown(ch[p][r]);
    if (siz[ch[ch[p][r]][!r]] >= siz[ch[p][r]] * (1 - alpha * 2) / (1 - alpha))
      rotate(ch[p][r], !r);
    rotate(p, r);
  }
  int newnode(int v) {
    int p = tct ? tsh[tct--] : ++tot;
    val[p] = v;
    ch[p][0] = ch[p][1] = 0;
    siz[p] = 1;
    return p;
  }
  void insert(int p, int v) {
    if (isleaf(p)) {
      ch[p][0] = newnode(val[p]);
      ch[p][1] = newnode(v);
      if (val[ch[p][0]] > val[ch[p][1]]) swap(ch[p][0], ch[p][1]);
    } else {
      pushdown(p);
      insert(ch[p][val[ch[p][0]] < v], v);
    }
    maintain(p);
    update(p);
  }
  void erase(int p, int v) {
    pushdown(p);
    int r = val[ch[p][0]] < v;
    if (isleaf(ch[p][r])) {
      if (val[ch[p][r]] != v) return;
      destroy(ch[p][0]), destroy(ch[p][1]);
      int q = ch[p][!r];
      memcpy(ch[p], ch[q], sizeof ch[p]);
      val[p] = val[q];
      siz[p] = siz[q];
    } else {
      erase(ch[p][r], v);
    }
    maintain(p);
    update(p);
  }
  int getrnk(int p, int v) {
    int res = 0;
    while (!isleaf(p)) {
      pushdown(p);
      int r = val[ch[p][0]] < v;
      if (r) res += siz[ch[p][0]];
      p = ch[p][r];
    }
    return res + (val[p] < v);
  }
  int getkth(int p, int k) {
    k += 1;
    while (!isleaf(p)) {
      pushdown(p);
      int r = k > siz[ch[p][0]];
      if (r) k -= siz[ch[p][0]];
      p = ch[p][r];
    }
    return val[p];
  }
  int merge(int p, int q) {
    if (!p || !q) return p + q;
    if (min(siz[p], siz[q]) >= alpha * (siz[p] + siz[q])) {
      int t = newnode(0);
      ch[t][0] = p, ch[t][1] = q;
      maintain(t);
      return t;
    }
    if (siz[p] >= siz[q]) {
      pushdown(p);
      if (siz[ch[p][0]] >= alpha * (siz[p] + siz[q])) {
        ch[p][1] = merge(ch[p][1], q);
      } else {
        pushdown(ch[p][1]);
        ch[p][0] = merge(ch[p][0], ch[ch[p][1]][0]);
        ch[p][1] = merge(ch[ch[p][1]][1], q);
      }
      maintain(p);
      return p;
    } else {
      pushdown(q);
      if (siz[ch[q][1]] >= alpha * (siz[p] + siz[q])) {
        ch[q][0] = merge(p, ch[q][0]);
      } else {
        pushdown(ch[q][0]);
        ch[q][1] = merge(ch[ch[q][0]][1], ch[q][1]);
        ch[q][0] = merge(p, ch[ch[q][0]][0]);
      }
      maintain(q);
      return q;
    }
  }
  void split(int p, int k, int &x, int &y) {
    if (!k) return x = 0, y = p, void();
    if (isleaf(p)) return x = p, y = 0, void();
    pushdown(p);
    if (k <= siz[ch[p][0]]) {
      split(ch[p][0], k, x, y);
      y = merge(y, ch[p][1]);
    } else {
      split(ch[p][1], k - siz[ch[p][0]], x, y);
      x = merge(ch[p][0], x);
    }
    destroy(p);
  }
  void dfs(int p) {
    pushdown(p);
    if (isleaf(p)) {
      if (val[p] > 0) cout << val[p] << " ";
      else debug("-inf ");
    } else {
      dfs(ch[p][0]);
      dfs(ch[p][1]);
    }
  }
  void print(int p) {
    if (!isleaf(p)) print(ch[p][0]),print( ch[p][1]);
    debug("ch[%d] = {%d, %d}\n", p, ch[p][0], ch[p][1]);
  }
};
WBLT<300010> t;
int main() {
  int n, m;
  cin >> n >> m;
  for (int i = 1; i <= n; i++) t.insert(t.root, i);
  for (int i = 1; i <= m; i++) {
    int l, r;
    cin >> l >> r;
    debug("l = %d, r = %d\n", l, r);
    int x, y, z;
    t.split(t.root, l, x, y);
    t.split(y, r - l + 1, y, z);
    t.spread(y);
    t.root = t.merge(x, t.merge(y, z));
  }
  t.dfs(t.root), cout << endl;
  return 0;
}