可持久化线段树（主席树）

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

  void push_up(int p) {
    info[p].cnt = info[info[p].ls].cnt + info[info[p].rs].cnt;
  }

  int New() {
    return ++idx;
  }

  int modify(int root, int l, int r, int x) {
    int p = New();
    info[p] = info[root];
        // 继承之前的信息，根据自身值得大小决定哪个儿子要新开节点

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

  i64 query(int lroot, int rroot, int l, int r, int k) {
    if (l == r) return l;
    int x = info[info[rroot].ls].cnt - info[info[lroot].ls].cnt; // cnt 就是值域中的数的个数！
    int mid = l + r >> 1;
    if (k <= x) {
      return query(info[lroot].ls, info[rroot].ls, l, mid, k);
    } else {
      return query(info[lroot].rs, info[rroot].rs, mid + 1, r, k - x);
    }
  }
  i64 query(int x, int y, int k) {
    return query(x, y, 1, n, k);
  }
};

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