可持久化线段树(主席树)
0. 前置知识:
权值线段树, 离散化, 前缀和。
1. 问题引入:
对于给定的静态区间,求 (kth)。
2. 解决方法:
主席树,更具体一点就是可持久化权值线段树。可持久化就是要把以前的历史版本的信息都存储下来。每一个版本都是一颗权值线段树,权值线段树中维护的是值域中的数一共出现的次数,然后利用前缀和的思想可以很容易求出 (kth)。
3. 具体细节:
-
变量
- (lc:) 左儿子编号
- (rc:) 右儿子编号
- (root[i]:) 版本 (i) 的根
- (cnt:) 对应区间的数的个数
-
建树
对于新版本,我们要利用最近的历史版本来优化我们建树的过程。例如对于数列:(1,2,2,4,5,6)。我们已经建好的树如下:
目前版本是只有 (1,2,2,4) 的,接下来的一个版本是要将 (5) 插入了。插入结果如下:
-
查询
对于查询 ([l, r]) 中的 (kth),我们发现在版本 (root[r].cnt - root[l-1].cnt) 就是区间 ([l, r]) 中的数的个数, 那么我们很容易就可以求出 (kth)。
4. 具体代码
/*
@Author: nonameless
@Date: 2020-05-31 10:00:15
@Email: 2835391726@qq.com
@Blog: https://www.cnblogs.com/nonameless/
*/
#include <bits/stdc++.h>
#define x first
#define y second
#define pb push_back
#define sz(x) (int)x.size()
#define all(x) x.begin(), x.end()
using namespace std;
typedef long long ll;
typedef pair<ll, ll> PLL;
typedef pair<int, int> PII;
const double eps = 1e-8;
const double PI = acos(-1.0);
const int INF = 0x3f3f3f3f;
const ll LNF = 0x3f3f3f3f3f3f;
inline int gcd(int a, int b) { return b ? gcd(b, a % b) : a; }
inline ll gcd(ll a, ll b) { return b ? gcd(b, a % b) : a; }
inline int lcm(int a, int b) { return a * b / gcd(a, b); }
const int N = 2e5 + 10;
struct Node{
int lc, rc;
int cnt;
}tr[N << 5];
int n, m, idx = 0;
int a[N], root[N];
vector<int> nums;
int find(int x){
return lower_bound(all(nums), x) - nums.begin() + 1;
}
void build(int &p, int l, int r){
p = ++ idx;
if(l == r) return;
int mid = l + r >> 1;
build(tr[p].lc, l, mid);
build(tr[p].rc, mid + 1, r);
}
int insert(int p, int l, int r, int x){
int q = ++ idx;
tr[q] = tr[p]; // 先复制历史版本的信息
if(l == r) { tr[q].cnt ++; return q; }
int mid = l + r >> 1;
// 判断 x 在那个区间,那么对应区间就需要新建一个结点
if(mid >= x) tr[q].lc = insert(tr[p].lc, l, mid, x);
else tr[q].rc = insert(tr[p].rc, mid + 1, r, x);
tr[q].cnt = tr[tr[q].lc].cnt + tr[tr[q].rc].cnt;
return q;
}
int query(int p, int q, int l, int r, int k){
if(l == r) return l;
int mid = l + r >> 1;
// 计算 [l, mid] 中的数的个数来判断 kth 是在 [l, mid] 中还是在 [mid + 1, r] 中
int cnt = tr[tr[p].lc].cnt - tr[tr[q].lc].cnt;
if(cnt >= k) return query(tr[p].lc, tr[q].lc, l, mid, k);
else return query(tr[p].rc, tr[q].rc, mid + 1, r, k - cnt);
}
int main(){
cin >> n >> m;
for(int i = 1; i <= n; i ++){
scanf("%d", &a[i]);
nums.pb(a[i]);
}
// 离散化
sort(all(nums));
nums.erase(unique(all(nums)), nums.end());
int len = sz(nums);
// 建一颗空树
build(root[0], 1, len);
// 依次插入每个数并建树
for(int i = 1; i <= n; i ++)
root[i] = insert(root[i - 1], 1, len, find(a[i]));
while(m -- ){
int l, r, k;
scanf("%d%d%d", &l, &r, &k);
printf("%d
", nums[query(root[r], root[l - 1], 1, len, k) - 1]);
}
return 0;
}