ACWING 255. 第K小数（可持久化线段树，静态）

本文主要是介绍ACWING 255. 第K小数（可持久化线段树，静态），希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

给定长度为N的整数序列A，下标为 1∼N。

现在要执行M次操作，其中第i次操作为给出三个整数li,ri,ki，求A[li],A[li+1],…,Ari中第ki小的数是多少。

输入格式
第一行包含两个整数N和M。

第二行包含N个整数，表示整数序列A。

接下来M行，每行包含三个整数li,ri,ki，用以描述第i次操作。

输出格式
对于每次操作输出一个结果，表示在该次操作中，第k小的数的数值。

每个结果占一行。

数据范围
N≤105,M≤104,|A[i]|≤109
输入样例：
7 3
1 5 2 6 3 7 4
2 5 3
4 4 1
1 7 3
输出样例：
5
6
3

思路：
参考学习的博客
https://www.cnblogs.com/dmoransky/p/11427498.html

可持久化线段树就是每次修改利用了之前的信息。

于是我们每次单点修改实际上新建了一个线段树，与旧有线段树相同的部分直接相连，修改的部分则新建节点，每次单调修改增加 $l o g n$ 个点

线段树上每个节点维护对应权值出现的次数，则求第 $l, r$ 中 $k$ 大的数，就是求第 $r$ 次修改后减去第 $l - 1$ 次修改后线段树的第 $k$ 大值，相当于前缀和二分。

这个过程可以用权值线段树动态开点实现。

#include <cstdio>
#include <cstring>
#include <algorithm>using namespace std;const int maxn = 1e5 + 7;int n,m,len,a[maxn],b[maxn];struct Tree {int l,r,v;
}t[maxn * 20];int T[maxn],tot;int build(int l,int r) {int p = ++tot,mid = (l + r) >> 1;if(l < r) {t[p].l = build(l,mid);t[p].r = build(mid + 1,r);}t[p].v = 0;return p;
}int update(int pre,int l,int r,int v) {int p = ++tot;int mid = (l + r) >> 1;t[p].l = t[pre].l;t[p].r = t[pre].r;t[p].v = t[pre].v + 1;if(l < r) {if(v <= mid) {t[p].l = update(t[pre].l,l,mid,v);} else {t[p].r = update(t[pre].r,mid + 1,r,v);}}return p;
}int query(int x,int y,int l,int r,int k) {if(l == r) return l;int sum = t[t[y].l].v - t[t[x].l].v;int mid = (l + r) >> 1;if(k <= sum) {return query(t[x].l,t[y].l,l,mid,k);} else {return query(t[x].r,t[y].r,mid + 1,r,k - sum);}
}int main() {scanf("%d%d",&n,&m);for(int i = 1;i <= n;i++) {scanf("%d",&a[i]);b[i] = a[i];}sort(b + 1,b + 1 + n);len = unique(b + 1,b + 1 + n) - (b + 1);for(int i = 1;i <= n;i++) {a[i] = lower_bound(b + 1,b + 1 + len,a[i]) - b;}T[0] = build(1,len);for(int i = 1;i <= n;i++) {T[i] = update(T[i - 1],1,len,a[i]);}for(int i = 1;i <= m;i++) {int x,y,k;scanf("%d%d%d",&x,&y,&k);printf("%d\n",b[query(T[x - 1],T[y],1,len,k)]);}return 0;
}