记录编号 |
481184 |
评测结果 |
AAAAAAAAAA |
题目名称 |
[河南省队2012] 找第k小的数 |
最终得分 |
100 |
用户昵称 |
Shirry |
是否通过 |
通过 |
代码语言 |
C++ |
运行时间 |
1.054 s |
提交时间 |
2018-01-01 18:16:14 |
内存使用 |
36.15 MiB |
显示代码纯文本
#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
const int maxn=100010;
const int maxm=maxn*30;
struct poi{
int x,id;
bool operator < (const poi&b)const{
return x<b.x;
}
}a[maxn];
int sz,tr[maxn],lc[maxm],rc[maxm],rnk[maxn],sum[maxm];
void insert(int &x,int last,int l,int r,int d){
x=++sz;
if(l==r)sum[x]=sum[last]+1;
else{
int mid=(l+r)>>1;
lc[x]=lc[last],rc[x]=rc[last];
if(d<=mid)insert(lc[x],lc[last],l,mid,d);
else insert(rc[x],rc[last],mid+1,r,d);
sum[x]=sum[lc[x]]+sum[rc[x]];
}
}
int findkth(int x,int last,int l,int r,int k){
if(l==r)return l;
int mid=(l+r)>>1;
int tmp=sum[lc[x]]-sum[lc[last]];
if(k<=tmp)return findkth(lc[x],lc[last],l,mid,k);
else return findkth(rc[x],rc[last],mid+1,r,k-tmp);
}
int main(){
freopen("kth.in","r",stdin);
freopen("kth.out","w",stdout);
int n,m,l,r,k;
scanf("%d%d",&n,&m);
for(int i=1;i<=n;i++)scanf("%d",&a[i].x),a[i].id=i;
sort(a+1,a+1+n);
for(int i=1;i<=n;i++)rnk[a[i].id]=i;
for(int i=1;i<=n;i++)insert(tr[i],tr[i-1],1,n,rnk[i]);
for(int i=1;i<=m;i++){
scanf("%d%d%d",&l,&r,&k);
printf("%d\n",a[findkth(tr[r],tr[l-1],1,n,k)].x);
}
return 0;
}