题目
给定长度为 N 的整数序列 A,下标为 1∼N。
现在要执行 M 次操作,其中第 i 次操作为给出三个整数 li,ri,ki,求 A[li],A[li+1],…,A[ri] (即 A 的下标区间 [li,ri])中第 ki 小的数是多少。
思路
可持续化线段树
从第一个值往后更新,每插入一个数,他只会影响从根节点到子节点logN长度上的所有节点,所以设可持久化线段树减少空间浪费
每次更新用一个数组root来记录根节点的标号,建立空树的时候idx=4N,所以第一个插入的根节点编号应该=4N+1,第二个=4N+logN+1,以此类推最后一个插入以后编号=4N+NlogN
如果要找l,r区间内的第k小树,root[r]记录的是从1插入到r,root[l-1]记录的是从1插入到l,那么只要通过这两个根节点相减,就能得到插入l到r的记录,具体看代码
每个节点都记录一下以该节点为根的叶子数量,因为叶子编号1、2···n即等于容器中第i个小的数(相当于离散化),那么如果k<=该节点左子树的数量,说明第k小的数应该在根的左子树内,反之在右子树内
代码
#include<bits/stdc++.h>
using namespace std;
#define int long long
const int N=1e5+5;
int root[N],a[N],idx;
struct node{
int l,r,cnt;
}tr[N*4+N*17];
int build(int l,int r){
int p=++idx;
if(l==r)return p;
int mid=l+r>>1;
tr[p].l=build(l,mid);
tr[p].r=build(mid+1,r);
return p;
}
vector<int>v;
int find(int x){
return lower_bound(v.begin(),v.end(),x)-v.begin();
}
int insert(int pre,int l,int r,int x){
int p=++idx;
tr[p]=tr[pre];
if(l==r){
tr[p].cnt++;
return p;
}
int mid=l+r>>1;
if(x<=mid)tr[p].l=insert(tr[pre].l,l,mid,x);
else tr[p].r=insert(tr[pre].r,mid+1,r,x);
tr[p].cnt=tr[tr[p].l].cnt+tr[tr[p].r].cnt;
return p;
}
int query(int L,int R,int l,int r,int k){
if(l==r)return l;
int cnt=tr[tr[R].l].cnt-tr[tr[L].l].cnt;
int mid=l+r>>1;
if(k<=cnt)return query(tr[L].l,tr[R].l,l,mid,k);
else return query(tr[L].r,tr[R].r,mid+1,r,k-cnt);
}
signed main(){
ios::sync_with_stdio(false),cin.tie(0),cout.tie(0);
int n,m;
cin>>n>>m;
for(int i=1;i<=n;i++){
cin>>a[i];
v.push_back(a[i]);
}
sort(v.begin(),v.end());
v.erase(unique(v.begin(),v.end()),v.end());
root[0]=build(0,v.size()-1);
for(int i=1;i<=n;i++){
root[i]=insert(root[i-1],0,v.size()-1,find(a[i]));
}
while(m--){
int l,r,k;
cin>>l>>r>>k;
cout<<v[query(root[l-1],root[r],0,v.size()-1,k)]<<'\n';
}
return 0;
}