关于空间，第零棵树是 (4n)，其后每棵树都要多来 (log(n)) 的空间，所以我是开 (n(4+log(n))) 的空间。
关于借用节点：
图片来自这里
#include <algorithm>
#include <iostream>
#include <cstdio>
using namespace std;
int n, m, rot[200005], a[200005], b[200005], sum[4400005], lson[4400005];
int rson[4400005], uu, vv, ww, r, cnt;
int build(int l, int r){
int rt=++cnt;
int mid=(l+r)>>1;
sum[rt] = 0;
if(l<r){
lson[rt] = build(l, mid);
rson[rt] = build(mid+1, r);
}
return rt;
}
int update(int pre, int l, int r, int x){//pre就是rt准备“借”的那棵树
int rt=++cnt;
int mid=(l+r)>>1;
lson[rt] = lson[pre]; rson[rt] = rson[pre]; sum[rt] = sum[pre] + 1;
if(l<r){
if(x<=mid) lson[rt] = update(lson[pre], l, mid, x);
else rson[rt] = update(rson[pre], mid+1, r, x);
}
return rt;
}
int query(int uu, int vv, int l, int r, int k){
if(l>=r) return l;
int x=sum[lson[vv]]-sum[lson[uu]];
int mid=(l+r)>>1;
if(x>=k) return query(lson[uu], lson[vv], l, mid, k);
else return query(rson[uu], rson[vv], mid+1, r, k-x);
}
int main(){
cin>>n>>m;
for(int i=1; i<=n; i++){
scanf("%d", &a[i]);
b[i] = a[i];
}
sort(b+1, b+1+n);
r = unique(b+1, b+1+n) - (b + 1);
rot[0] = build(1, r);
for(int i=1; i<=n; i++){
int t=lower_bound(b+1, b+1+r, a[i])-b;//快速找出a[i]在整个不可重数组中的位置
rot[i] = update(rot[i-1], 1, r, t);
}
while(m--){
scanf("%d %d %d", &uu, &vv, &ww);
printf("%d
", b[query(rot[uu-1], rot[vv], 1, r, ww)]);
}
return 0;
}