P3834 【模板】可持久化线段树 2

先用结构体实现了下，发现写错了（只有20分），后面直接用的数组了

#include<bits/stdc++.h>
using namespace std;

const int N = 2e5 + 7;

int tl[N << 6], tr[N << 6], sum[N << 6];
int cnt, a[N], v[N], rt[N];

int build(int l, int r){
　　int p = ++ cnt;
　　sum[p] = 0;
　　if(l == r)
　　　　return p;
　　int mid = (l + r) >> 1;
　　tl[p] = build(l, mid);
　　tr[p] = build(mid + 1, r);
　　return p;
}

int insert(int l, int r, int val, int pre){
　　int p = ++ cnt;
　　tl[p] = tl[pre], tr[p] = tr[pre];
　　sum[p] = sum[pre] + 1;
　　if(l == r) return p;
　　int mid = (l + r) >> 1;
　　if(val <= mid) tl[p] = insert(l, mid, val, tl[pre]);
　　else tr[p] = insert(mid + 1, r, val, tr[pre]);
　　return p;
}

int query(int prel, int prer, int k, int l, int r){
　　if(l == r)
　　　　return v[l];
　　int suml = sum[tl[prer]] - sum[tl[prel]];
　　int mid = (l + r) >> 1;
　　if(k <= suml) return query(tl[prel], tl[prer], k, l, mid);
　　else return query(tr[prel], tr[prer], k - suml, mid + 1, r);
}

int main(){
　　int n, q;
　　scanf("%d%d", &n, &q);
　　for(int i = 1;i <= n;i ++){
　　　　scanf("%d", &a[i]);
　　　　v[i] = a[i];
　　}
　　sort(v + 1, v + n + 1);
　　int t = unique(v + 1, v + n + 1) - v - 1;
　　rt[0] = build(1, t);

　　for(int i = 1;i <= n;i ++){
　　　　int val = lower_bound(v + 1, v + t + 1, a[i]) - v;
　　　　rt[i] = insert(1, n, val, rt[i - 1]);
　　}
　　while(q --){
　　　　int l, r, k;
　　　　scanf("%d%d%d", &l, &r, &k);
　　　　printf("%d\n", query(rt[l - 1], rt[r], k, 1, n));
　　}
　　return 0;
}