题目描述
看到很短的题目会让人心情愉悦，所以给出一个长度为N的序列A1,A2,A3,...,AN，
现在有M个询问，每个询问都是Ai...Aj中第k小的数等于多少。
- 输入格式
- 第一行两个正整数N，M。
- 第二行N个数，表示序列A1,A2,...,AN。
- 紧着的M行，每行三个正整数i,j,k(k≤j-i+1)，表示
询问Ai...Aj中第k小的数等于多少。
- 输出格式
共输出M行，第i行输出第i个询问的答案。
- 样例输入1：
4 3
4 1 2 3
1 3 1
2 4 3
1 4 4
- 样例输出1：
- 1
- 3
- 4
- 样例输入2：
- 5 5
- 4 2 9 9 10
- 1 3 1
- 2 4 3
- 1 4 4
- 3 5 2
- 2 5 2
- 样例输出2：
- 2
- 9
- 9
- 9
- 9
- 注释：
- 询问区间的第k小值并非严格第k小，例如样例2中第4个询问，询问3到5中第2小的数，
- 答案输出9，并不是严格第2小的10。
- 数据范围：
- 在50%的数据中，1<=N<=10000，1<=M<=10000，A[i]<=100000;
- 在100%的数据中，1<=N<=100000,1<=M<=100000,A[i]<=1000000;
- 主席树求静态区间k大值模板
#include <algorithm>
#include <cstdio>
#define N 100500
using namespace std;
struct cmt
{
int l,r,size;
}tr[N*];
int n,m,rt[N],tot,a[N],b[N],size;
int build(int l,int r)
{
int now=++tot;
tr[now].size=;
if(l==r) return now;
int mid=(l+r)>>;
tr[now].l=build(l,mid);
tr[now].r=build(mid+,r);
return now;
}
inline int Rank(int x)
{
return lower_bound(b+,b++size,x)-b;
}
void update(int l,int r,int x,int &y,int t)
{
y=++tot;
tr[y].size=tr[x].size+;
if(l==r) return;
tr[y].l=tr[x].l;
tr[y].r=tr[x].r;
int mid=(l+r)>>;
if(t<=mid) update(l,mid,tr[x].l,tr[y].l,t);
else update(mid+,r,tr[x].r,tr[y].r,t);
}
int ask(int l,int r,int lx,int rx,int k)
{
if(l==r) return l;
int mid=(l+r)>>;
if(tr[tr[rx].l].size-tr[tr[lx].l].size>=k) return ask(l,mid,tr[lx].l,tr[rx].l,k);
else {k-=tr[tr[rx].l].size-tr[tr[lx].l].size;return ask(mid+,r,tr[lx].r,tr[rx].r,k);}
}
int Main()
{
freopen("kth.in","r",stdin);
freopen("kth.out","w",stdout);
scanf("%d%d",&n,&m);
for(int i=;i<=n;++i) scanf("%d",&a[i]),b[i]=a[i];
sort(b+,b++n);
size=unique(b+,b++n)-b-;
rt[]=build(,size);
for(int i=;i<=n;++i) update(,size,rt[i-],rt[i],Rank(a[i]));
for(int l,r,k;m--;)
{
scanf("%d%d%d",&l,&r,&k);
printf("%d\n",b[ask(,size,rt[l-],rt[r],k)]);
}
return ;
}
int sb=Main();
int main(int argc,char *argv[]) {;}