洛谷 P3834 【模板】可持久化线段树 1（主席树）

Description:

这是个非常经典的主席树入门题——静态区间第K小

数据已经过加强，请使用主席树。同时请注意常数优化

如题，给定N个整数构成的序列，将对于指定的闭区间查询其区间内的第K小值。

Input:

第一行包含两个正整数N、M，分别表示序列的长度和查询的个数。

第二行包含N个整数，表示这个序列各项的数字。

接下来M行每行包含三个整数 $l, r, k$ , 表示查询区间 $[l, r]$ 内的第k小值。

对于20%的数据满足： $1 \leq N, M \leq 10$

对于50%的数据满足： $1 \leq N, M \leq 1 0^{3}$

对于80%的数据满足： $1 \leq N, M \leq 1 0^{5}$

对于100%的数据满足： $1 \leq N, M \leq 2 \cdot 1 0^{5}$

对于数列中的所有数 $a_{i}$ ，均满足 $- 10^{9} \leq a_{i} \leq 10^{9}$

样例数据说明：

N=5，数列长度为5，数列从第一项开始依次为 $[25957, 6405, 15770, 26287, 26465]$

第一次查询为 $[2, 2]$ 区间内的第一小值，即为6405

第二次查询为 $[3, 4]$ 区间内的第一小值，即为15770

第三次查询为 $[4, 5]$ 区间内的第一小值，即为26287

第四次查询为 $[1, 2]$ 区间内的第二小值，即为25957

第五次查询为 $[4, 4]$ 区间内的第一小值，即为26287

Output:

输出包含k行，每行1个整数，依次表示每一次查询的结果

Sample Input:

5 5
25957 6405 15770 26287 26465
2 2 1
3 4 1
4 5 1
1 2 2
4 4 1

Sample Output:

6405
15770
26287
25957
26287

题目链接

区间静态第 $k$ 小，可持久化线段树（也称主席树）模板题

可持久化线段树的原理为对 $[1, n]$ 区间内每个前缀建立一棵线段树，之后通过前缀和的思想进行 $[l, r]$ 区间内线段树减法（第 $r$ 棵线段树减第 $l - 1$ 棵线段树）来求第 $k$ 小

但这样的做法需耗费巨大的空间（ $n$ 棵线段树每棵 $4$ 倍空间），所以在可持久化线段树上两相邻线段树只有一个节点有变化，所以其余节点可公用（这样就不能通过 $o < < 1$ 和 $o < < 1 ∣ 1$ 来定位节点的左右孩子节点，所以需要两个数组记录节点的左右孩子信息），这样就可以减小很多内存空间的使用

AC代码:

#include <cstdio>
#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
const int maxn = 2e5 + 5;

class func_seg_tree {
  public:
    int tot;
    int rt[maxn];
    int lson[maxn << 5], rson[maxn << 5];
    int cnt[maxn << 5];

    int Build(int l, int r) {
      int t = ++tot;
      int m = (l + r) >> 1;
      if (l != r) {
        lson[t] = Build(l, m);
        rson[t] = Build(m + 1, r);
      }
      return t;
    }

    void Init(int n) {
      tot = 0;
      rt[0] = Build(1, n);
    }

    int Modify(int prev, int l, int r, int x) {
      int t = ++tot;
      lson[t] = lson[prev]; rson[t] = rson[prev];
      cnt[t] = cnt[prev] + 1;
      int m = (l + r) >> 1;
      if (l != r) {
        if (x <= m) lson[t] = Modify(lson[t], l, m, x);
        else rson[t] = Modify(rson[t], m + 1, r, x);
      }
      return t;
    }

    int Query(int u, int v, int l, int r, int k) {
      if (l == r) return l;
      int m = (l + r) >> 1;
      int num = cnt[lson[v]] - cnt[lson[u]];
      if (num >= k) return Query(lson[u], lson[v], l, m, k);
      return Query(rson[u], rson[v], m + 1, r, k - num);
    }
};

class Hash {
  public:
    int size;
    vector<int> arr;

    Hash(const vector<int> &v) {
      arr.assign(v.begin(), v.end());
      sort(arr.begin(), arr.end());
      arr.erase(unique(arr.begin(), arr.end()), arr.end());
      size = arr.size();
    }

    int Get(int k) {
      return lower_bound(arr.begin(), arr.end(), k) - arr.begin();
    }
};

func_seg_tree fsgt;

int main() {
  ios::sync_with_stdio(false); cin.tie(0);
  int n, m; cin >> n >> m;
  vector<int> arr(n);
  for (int i = 0; i < n; ++i) cin >> arr[i];
  Hash h(arr);
  fsgt.Init(n);
  for (int i = 1; i <= n; ++i) fsgt.rt[i] = fsgt.Modify(fsgt.rt[i - 1], 1, h.size, h.Get(arr[i - 1]) + 1);
  for (int i = 0, l, r, k; i < m; ++i) {
    cin >> l >> r >> k;
    cout << h.arr[fsgt.Query(fsgt.rt[l - 1], fsgt.rt[r], 1, h.size, k) - 1] << endl;
  }
  return 0;
}