主席树求区间第K小模板

本文主要是介绍主席树求区间第K小模板，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

主席树（President Tree）是一种用于解决区间查询和修改问题的数据结构，通常用于静态区间问题（即查询和修改操作在构建结构之后不再发生变化）。主席树可以高效地处理诸如区间和、区间最值等问题。

主席树的实现原理：

基本思想：主席树是一种基于分治思想的数据结构，它将原始序列按照每个位置的取值范围进行离散化，然后构建出一棵持久化线段树（Persistent Segment Tree）。
持久化线段树：持久化线段树是线段树的一种扩展，它能够记录每次修改后的线段树版本，而不是像传统线段树那样每次都覆盖更新。通过这种方式，我们可以在保留历史版本的基础上进行有效的区间查询。
构建过程：首先对原始序列进行排序和离散化，然后根据每个位置的取值范围构建出持久化线段树。在构建过程中，每棵线段树都会继承前一棵线段树的所有信息，并根据具体的修改操作进行更新。
查询操作：利用持久化线段树，可以高效地进行区间查询操作，例如区间求和、区间最值等。

优点和应用：

主席树适用于静态区间问题，即查询和修改操作在构建结构之后不再发生变化的场景。
它能够高效地处理区间查询和修改问题，例如区间和、区间最值等。

总的来说，主席树是一种用于解决静态区间查询和修改问题的数据结构，通过离散化和持久化线段树的方式，能够高效地处理各种区间操作。希望这些信息能帮助你理解主席树的基本原理和应用场景。

题目

给定n个数，q次询问，每次求区间 [ l , r ] 中从小到大排序后第 k 个数。
1 <= n <= 100 000, 1 <= q <= 5 000，1 <=l <=r<= n, 1 <= k <= j - i + 1

示例

Input
7 3
1 5 2 6 3 7 4
2 5 3
4 4 1
1 7 3

Output
5
6
3

Code

#include <iostream>
#include<cstdio>
#include<algorithm>
#define midd (l+r)/2
using namespace std;
typedef long long ll;
const int N = 200010;
int n, q, sz, cnt = 0;
int a[N], b[N], T[N];//a为原数组,b为排序离散化数组,T[i]为(值)[1,i]的根节点
int sum[N<<5], L[N<<5], R[N<<5];inline int build(int l, int r)
{int rt = ++ cnt;sum[rt] = 0;if (l < r){L[rt] = build(l, midd);R[rt] = build(midd+1, r);}return rt;
}inline int update(int pre, int l, int r, int x)
{int rt = ++ cnt;L[rt] = L[pre]; R[rt] = R[pre]; sum[rt] = sum[pre]+1;if (l < r){if (x <= midd) L[rt] = update(L[pre], l, midd, x);else R[rt] = update(R[pre], midd+1, r, x);}return rt;
}inline int query(int u, int v, int l, int r, int k)//返回下标,即<=k个数
{if (l >= r) return l;int x = sum[L[v]] - sum[L[u]];if (x >= k) return query(L[u], L[v], l, midd, k);else return query(R[u], R[v], midd+1, r, k-x);
}int main()
{while(scanf("%d%d", &n, &q)!=EOF){cnt=0;for (int i = 1; i <= n; i ++){scanf("%d", &a[i]);b[i] = a[i];}sort(b+1, b+1+n);sz = unique(b+1, b+1+n)-b-1;T[0] = build(1, sz);for (int i = 1; i <= n; i ++){int t = lower_bound(b+1, b+1+sz, a[i])-b;T[i] = update(T[i-1], 1, sz, t);}while (q --){int l, r, k;scanf("%d%d%d", &l, &r ,&k);// k= r-l+1-k+1;//求第k大时改一下就行int idx=query(T[l-1], T[r], 1, sz, k);int ans=b[idx];printf("%d\n",ans);}}return 0;
}