题目描述
如题，给定 nnn 个整数构成的序列，将对于指定的闭区间查询其区间内的第 kkk 小值。
输入格式
第一行包含两个正整数 n,mn,mn,m，分别表示序列的长度和查询的个数。
第二行包含 nnn 个整数，表示这个序列各项的数字。
接下来 mmm 行每行包含三个整数 l,r,k l, r, kl,r,k , 表示查询区间 [l,r][l, r][l,r] 内的第 kkk 小值。
输出格式
输出包含 kkk 行，每行一个整数，依次表示每一次查询的结果
莫队+树状数组:O(nsqrt(n)logn*logn) 得分:80
#include<cmath>
#include<cstdio>
#include<cstring>
#include<iostream>
#include<algorithm>
using namespace std;
const int N=2e5+10;
int a[N],b[N],belong[N],n,m;
inline int read(){
int x=0,f=1; char c=getchar();
while(c<'0'||c>'9'){ if(c=='-')f=-1; c=getchar(); }
while('0'<=c&&c<='9'){ x=(x<<3)+(x<<1)+c-48; c=getchar(); }
return x*f;
}
struct node{
int l,r,k,id;
}e[N];
inline bool cmp(node t1,node t2){
return (belong[t1.l]^belong[t2.l])?t1.l<t2.l:t1.r<t2.r;
}
int c[N];
inline void Add(int x,int y){
for(;x<=n;x+=x&(-x))c[x]+=y;
}
inline int sum(int x){
int ans=0;
for(;x;x-=x&(-x))ans+=c[x];
return ans;
}
inline void add(int x){
Add(a[x],1);
}
inline void del(int x){
Add(a[x],-1);
}
inline int check(int mid){
return sum(mid);
}
inline int erfen(int x){
int l=0,r=n,ans=0;
while(l<=r){
int mid=(l+r)>>1;
if(check(mid)<x){
l=mid+1;
ans=mid;
}else r=mid-1;
}
return ans+1;
}
int ans[N];
signed main(){
n=read(); m=read();
int size=sqrt(n);
int num=ceil((double)n/size);
for(int i=1;i<=num;i++)
for(int j=(i-1)*size+1;j<=size*i;j++)
belong[j]=i;
for(int i=1;i<=n;i++)b[i]=a[i]=read();
sort(b+1,b+1+n);
for(int i=1;i<=n;i++)a[i]=lower_bound(b+1,b+1+n,a[i])-b;
for(int i=1;i<=m;i++)e[i].l=read(),e[i].r=read(),e[i].k=read(),e[i].id=i;;
sort(e+1,e+1+m,cmp);
int l=e[1].l,r=e[1].r,k;
for(int i=l;i<=r;i++)add(i);
for(int i=1;i<=m;i++){
while(l<e[i].l)del(l++);
while(l>e[i].l)add(--l);
while(r<e[i].r)add(++r);
while(r>e[i].r)del(r--);
k=e[i].k;
ans[e[i].id]=erfen(k);
}
for(int i=1;i<=m;i++)
printf("%d
",b[ans[i]]);
}