题目背景

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

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

题目描述

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

输入格式

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

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

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

输出格式

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

输入输出样例

输入 #1

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

输出 #1

1
2
3
4
5
6405
15770
26287
25957
26287

说明/提示

数据范围：

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

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

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

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

对于数列中的所有数 $a_i$ ，均满足c$-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$

题意、解决方案

模板题，存个板子

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
#include <bits/stdc++.h>
#define zpw                    \
  ios::sync_with_stdio(false); \
  cin.tie(NULL);               \
  cout.tie(NULL)

using namespace std;

const int maxn = 2e5 + 10;

struct node {
  int lch, rch, sum;
} tree[maxn * 40];

int a[maxn];
int b[maxn];
int root[maxn];
int tot;

/* [l ,r] 当前区间, rt 当前树节点编号 */
void build(int l, int r, int& rt) {
  rt = tot++;
  tree[rt].sum = 0;
  if (l == r) {
    return;
  }
  int m = (l + r) >> 1;
  build(l, m, tree[rt].lch);
  build(m + 1, r, tree[rt].rch);
}

/* [l, r] 当前区间, rt 当前树节点编号, pre 前一棵线段树的当前节点, c 更新的点 */
void update(int l, int r, int& rt, int pre, int c) {
  rt = tot++;
  tree[rt] = tree[pre];
  tree[rt].sum += 1;
  if (l == r) {
    return;
  }
  int m = (l + r) >> 1;
  if (c <= m) {
    update(l, m, tree[rt].lch, tree[pre].lch, c);
  } else {
    update(m + 1, r, tree[rt].rch, tree[pre].rch, c);
  }
}

/* [l, r] 当前区间, rt 当前树节点编号, pre 前一棵线段树的当前节点, 第 k 小 */
int query(int l, int r, int rt, int pre, int k) {
  if (l == r) {
    return l;
  }
  int m = (l + r) >> 1;
  int lnum = tree[tree[rt].lch].sum - tree[tree[pre].lch].sum;
  if (lnum >= k) {
    return query(l, m, tree[rt].lch, tree[pre].lch, k);
  } else {
    return query(m + 1, r, tree[rt].rch, tree[pre].rch, k - lnum);
  }
}

int main() {
  int n, m;
  scanf("%d%d", &n, &m);
  for (int i = 1; i <= n; i++) {
    scanf("%d", &a[i]);
    b[i] = a[i];
  }
  /* 离散化 */
  sort(b + 1, b + n + 1);
  int num = unique(b + 1, b + n + 1) - (b + 1);
  build(1, num, root[0]);
  for (int i = 1; i <= n; i++) {
    int p = lower_bound(b + 1, b + num + 1, a[i]) - b;
    update(1, num, root[i], root[i - 1], p);
  }
  while (m--) {
    int l, r, k;
    scanf("%d%d%d", &l, &r, &k);
    int p = query(1, num, root[r], root[l - 1], k);
    printf("%d\n", b[p]);
  }
  return 0;
}