线段树合并

const int N = ${1:this} + 5;
// 总点数为 nlog(n) * C
const int M = 4e6 + 5;

template<class Info>
struct SegmentTree {
  int n;
  int idx = 0;
  vector<int> root;
  vector<int> rub;
  vector<Info> info;
  SegmentTree() : n(0) { }
  SegmentTree(int n_) {
    n = n_;
    root.assign(n + 1, 0);
    info.assign(M, Info());
  }

  void push_up(int p) {

  }

  // 千万注意 push_down 只有儿子存在的时候才加上 info[p].tag！！！
  void push_down(int p) {
    if (!info[p].tag) return;
    if (info[p].ls) {

    }
    if (info[p].rs) {

    }
    info[p].tag = 0;
  }

  int New() {
    if (!rub.empty()) {
      int res = rub.back();
      rub.pop_back();
      return res;
    }
    return ++idx;
  }

  void Del(int &p) {
    info[p] = Info();
    rub.emplace_back(p);
    p = 0;
  }

  // 调用： tr.modify(tr.root[u], x, v)
  // 一颗新的树直接 modify(tr.root[p], x, v) 因为 0 会自动给赋值！!！
  void modify(int &p, int l, int r, int x, const Info &v) {
    if (!p) p = New();
    if (l == r) {

      return;
    }
    int mid = l + r >> 1;
    if (x <= mid) {
      modify(info[p].ls, l, mid, x, v);
    } else {
      modify(info[p].rs, mid + 1, r, x, v);
    }
    push_up(p);
  }
  void modify(int &root, int x, const Info &v) {
    modify(root, 1, n, x, v);
  }

  // 调用 merge(tr.root[p], tr.root[q])，把 root[q] 合并到 root[p] 里面
  // 合并的时候进行一个后序遍历，可以直接把答案维护出来！！！
  int merge(int p, int q, int l, int r) {
    if (!p) {

      // 记得更新再走！！！

      return q;
    }
    if (!q) return p;
    if (l == r) {

      // 先更新答案，再更新 info[q]

      Del(q);
      return p;
    }
    int mid = l + r >> 1;
    info[p].ls = merge(info[p].ls, info[q].ls, l, mid);
    info[p].rs = merge(info[p].rs, info[q].rs, mid + 1, r);
    push_up(p);
    Del(q);
    return p;
  }
  void merge(int r1, int r2) {
    merge(r1, r2, 1, n);
  }

  // split(tr.root[p], tr.root[q], x, y) 其中 root[q] 为 0 也没有关系！!！
  void split(int &p, int &q, int l, int r, int x, int y) {
    if (l > y || r < x) return;
    if (!p) return;
    if (x <= l && r <= y) {
      q = p;
      p = 0;
      return;
    }
    if (!q) q = New();
    int mid = l + r >> 1;
    if (x <= mid) split(info[p].ls, info[q].ls, l, mid, x, y);
    if (mid < y) split(info[p].rs, info[q].rs, mid + 1, r, x, y);
    push_up(p);
    push_up(q);
  }
  void split(int &p, int&q, int x, int y) {
    split(p, q, 1, n, x, y);
  }

  i64 query(int p, int l, int r, int x, int y) {
    if (l > y || r < x) return 0LL;
    if (!p) return 0LL;
    if (l >= x && r <= y) {
      return info[p].cnt;
    }
    int mid = l + r >> 1;
    i64 res = 0;
    res += query(info[p].ls, l, mid, x, y);
    res += query(info[p].rs, mid + 1, r, x, y);
    return res;
  }
  i64 query(int root, int x, int y) {
    return query(root, 1, n, x, y);
  }
};

struct Info {
  int ls;
  int rs;
  int cnt;
  u64 val;
  Info() {
    ls = rs = val = cnt = 0;
  }
} info;