P1533 可怜的狗狗
可持久化线段树的板子题目
- 离散化(build);
- 查找(find);
#include<bits/stdc++.h>
using namespace std;
const int N = 3e5 + 7;
int a[N], hs[N];
int rt[N], tl[N << 6], tr[N << 6], s[N << 6], cnt = 1;
int build(int l, int r, int val, int pr){
int p = cnt;
s[p] = s[pr], tr[p] = tr[pr], tl[p] = tl[pr];
s[cnt ++] ++;
if(l == r) return p;
int mid = (l + r) >> 1;
if(mid >= val)tl[p] = build(l, mid, val, tl[pr]);
else tr[p] = build(mid + 1, r, val, tr[pr]);
return p;
}
int find(int l, int r,int x, int y, int k){
if(l == r) return hs[l];
int ans = s[tl[y]] - s[tl[x]];
int mid = (l + r) >> 1;
if(ans >= k) return find(l, mid, tl[x], tl[y], k);
else return find(mid + 1, r, tr[x], tr[y], k - ans);
}
int main(){
int n, m;
scanf("%d%d", &n, &m);
for(int i = 1;i <= n;i ++) scanf("%d", &a[i]), hs[i] = a[i];
sort(hs + 1, hs + n + 1);
int t = unique(hs + 1, hs + n + 1) - hs - 1;
for(int i = 1;i <= n;i ++){
int p = lower_bound(hs + 1, hs + t + 1, a[i]) - hs;
rt[i] = build(1, t, p, rt[i - 1]);
}
for(int i = 1;i <= m;i ++){
int l, r, v;
scanf("%d%d%d", &l, &r, &v);
printf("%d\n", find(1, t, rt[l - 1], rt[r], v));
}
return 0;
}