可持久化线段树

struct HJT {
  struct Node {
    int cnt;
    int l, r;
    Node(): l(0), r(0), cnt(0) {}
  };
  const int n;
  std::vector<Node> tr;
  std::vector<int> root;
  HJT(int n): n(n) {
    tr.emplace_back();
    root.push_back(0);
  }
  int insert(int p, int x, int l, int r) {
    int q = tr.size();
    tr.emplace_back();
    tr[q] = tr[p];
    if (l == r) {
      ++tr[q].cnt;
      return q;
    }
    int mid = l + r >> 1;
    if (x <= mid) tr[q].l = insert(tr[p].l, x, l, mid);
    else tr[q].r = insert(tr[p].r, x, mid + 1, r);
    tr[q].cnt = tr[tr[q].l].cnt + tr[tr[q].r].cnt;
    return q;
  }
  void insert(int x) {
    root.push_back(insert(root.back(), x, 0, n - 1));
  }
  int query(int p, int q, int L, int R, int l, int r) {
    if (L <= l && r <= R) return tr[q].cnt - tr[p].cnt;
    if (R < l || r < L) return 0;
    int mid = l + r >> 1;
    return query(tr[p].l, tr[q].l, L, R, l, mid) + query(tr[p].r, tr[q].r, L, R, mid + 1, r);
  }
  int query(int p, int q, int L, int R) {
    return query(root[p - 1], root[q], L, R, 0, n - 1);
  }
};