题目大意:给你一个数列和一些询问,每次询问你一个$[l,r]$区间里第k小数。
解题思路:可持久化线段树,所谓的“主席树”。对每一个$[1,l]$区间开一个线段树,运用主席树的可持久化,没有变化的子树直接用老版本的就行了。
然而你会发现,我代码里有个map,实际上是我用map记录离散值时TLE了。于是我把map换成了lower_bound()。所以STL的容器虽然方便,但速度并不快,能不用尽量不用。
C++ Code:
#include<cstdio>
#include<map>
#include<algorithm>
#include<cstring>
#define N 100005
using namespace std;
int n,m,root[N],d[N*20],node=0,mx;
int a[N],b[N];
int ld[N*20],rd[N*20];
map<int,int>mp;
void ins(int& cur,int t,int l,int r,int k){
cur=++node;
d[cur]=d[t];
d[cur]++;
ld[cur]=ld[t],rd[cur]=rd[t];
if(l==r)return;
int m=l+r>>1;
if(k<=m)ins(ld[cur],ld[t],l,m,k);else
ins(rd[cur],rd[t],m+1,r,k);
}
int query(int L,int R,int l,int r,int k){
if (k==0) return 0;
if(l==r)return l;
int ls=d[ld[R]]-d[ld[L]],m=l+r>>1;
if(d[R]-d[L]<k)return 0;
if(k<=ls)
return query(ld[L],ld[R],l,m,k);
return query(rd[L],rd[R],m+1,r,k-ls);
}
int main(){
scanf("%d%d",&n,&m);
for(int i=1;i<=n;++i)scanf("%d",&a[i]);
mx=n;
memcpy(b,a,sizeof b);
sort(b+1,b+n+1);
mx=unique(b+1,b+n+1)-b-1;
memset(root,0,sizeof root);
for(int i=1;i<=n;++i)ins(root[i],root[i-1],1,n,lower_bound(b+1,b+mx+1,a[i])-b);
while(m--){
int l,r,k;
scanf("%d%d%d",&l,&r,&k);
printf("%d\n",b[query(root[l-1],root[r],1,n,k)]);
}
return 0;
}