记录编号	454929	评测结果	AAAAAAAAAA
题目名称	[河南省队2012] 找第k小的数	最终得分	100
用户昵称	xyz117	是否通过	通过
代码语言	C++	运行时间	1.219 s
提交时间	2017-09-30 12:05:22	内存使用	53.70 MiB

#include <cstdio>
#include <cstring>
#include <cmath>
#include <algorithm>
using namespace std;
#define Q 1000010
#define N 1000010
#define lim 100000000
inline void read(int &s)
{
	s=0;
	int f=1;
	char ch=getchar();
	while(ch<'0'||ch>'9')
	{
		if(ch=='-')
			f=-1;
		ch=getchar();
	}
	while(ch>='0'&&ch<='9')
		s=s*10+ch-'0',ch=getchar();
	s*=f;
}
#define lowbit(x) x&(-x)
struct point
{
    int x,num;
}a[N];
struct query
{
    int x,y,k,cnt,num;
}q[Q],b[Q];
int sum[N],ans[Q];
int n,m;
bool cmp(const point&aa,const point&bb)
{
    return aa.x<bb.x;
}
void calc(int ll,int rr,int rawL,int mid)
{
    int L=1,R=n+1,MID;
    int i,j;
    while(L<R)
    {
        MID=(L+R)>>1;
        if(a[MID].x>=rawL)
            R=MID;
        else
            L=MID+1;
    }
    for(i=R;i<=n&&a[i].x<=mid;++i)
        for(j=a[i].num;j<=n;j+=lowbit(j))
            ++sum[j];
    for(i=ll;i<=rr;++i)
    {
        q[i].cnt=0;
        for(j=q[i].y;j;j-=lowbit(j))
            q[i].cnt+=sum[j];
        for(j=q[i].x-1;j;j-=lowbit(j))
            q[i].cnt-=sum[j];
    }
    for(i=R;i<=n&&a[i].x<=mid;++i)
        for(j=a[i].num;j<=n;j+=lowbit(j))
            --sum[j];
}
void divide(int ll,int rr,int rawL,int rawR)
{
	int i;
    if(rawL==rawR)
    {
        for(i=ll;i<=rr;++i)
            ans[q[i].num]=rawR;
        return;
    }
    int mid=rawL+((rawR-rawL)>>1);
    calc(ll,rr,rawL,mid);
    int now1=ll,now2=rr;
    for(i=ll;i<=rr;++i)
    {
        if(q[i].cnt>=q[i].k)
            b[now1++]=q[i];
        else
        {
            q[i].k-=q[i].cnt;
            b[now2--]=q[i];
        }
    }
    for(i=ll;i<=rr;++i)
        q[i]=b[i];
    if(now1!=ll)
        divide(ll,now1-1,rawL,mid);
    if(now2!=rr)
        divide(now2+1,rr,mid+1,rawR);
}
int main()
{
	freopen("kth.in","r",stdin);
	freopen("kth.out","w",stdout);
    read(n);
    read(m);
    for(int i=1;i<=n;++i)
    {
        read(a[i].x);
        a[i].num=i;
    }
    a[n+1].x=2e9;
    sort(a+1,a+1+n,cmp);
    for(int i=1;i<=m;++i)
    {
    	read(q[i].x);
    	read(q[i].y);
    	read(q[i].k);
        q[i].num=i;
    }
    divide(1,m,-lim,lim);
    for(int i=1;i<=m;++i)
        printf("%d\n",ans[i]);
    return 0;
}