记录编号	358977	评测结果	AAAAAEEEEE
题目名称	[河南省队2012] 找第k小的数	最终得分	50
用户昵称	sxysxy	是否通过	未通过
代码语言	C++	运行时间	3.892 s
提交时间	2016-12-20 09:18:26	内存使用	1.45 MiB

#include <cstdio>
#include <cstring>
#include <cstdlib>
#include <list>
#include <queue>
#include <vector>
#include <algorithm>
using namespace std;
struct node
{
    node *ls, *rs;
    int cnt;
    inline void pushup()
    {
        cnt = 0;
        if(ls)cnt += ls->cnt;
        if(rs)cnt += rs->cnt;
    }
    inline node()
    {
        ls = rs = NULL;
        cnt = 0;
    }
};
void insert(node *&x, int p, int L, int R)
{
    if(!x)x = new node();
    if(L == R && L == p){x->cnt++; return;}
    int M = (L+R)>>1;
    if(p <= M)insert(x->ls, p, L, M);
    else if(p > M)insert(x->rs, p, M+1, R);
    x->pushup();
}
int query(node *x, int ql, int qr, int L, int R)
{
    if(!x)return 0;
    if(ql <= L && R <= qr)return x->cnt;
    int M = (L+R)>>1, c = 0;
    if(ql <= M)c += query(x->ls, ql, qr, L, M);
    if(qr > M)c += query(x->rs, ql, qr, M+1, R);
    return c;
}
int L_LIMIT, R_LIMIT;
node *c[100002];
int n;
void add(int p, int v)
{
    for(; p <= n; p += p&-p)
        insert(c[p], v, L_LIMIT, R_LIMIT);
}
int query(int l, int r, int vl, int vr)
{
    int res = 0;
    for(; r; r -= r&-r)res += query(c[r], vl, vr, L_LIMIT, R_LIMIT);
    for(l--; l; l -= l&-l)res -= query(c[l], vl, vr, L_LIMIT, R_LIMIT);
    return res;
}
int kth(int l, int r, int k)
{
    int x = L_LIMIT, y = R_LIMIT;
    int ans;
    while(x <= y)
    {
        int m = (x+y)>>1;
        if(query(l, r, L_LIMIT, m) >= k)
        {
            ans = m;
            y = m-1;
        }else x = m+1;
    }
    return ans;
}
int a[100005];
int b[100004];
int main()
{
    freopen("kth.in", "r", stdin);
    freopen("kth.out", "w", stdout);
    int m;
    scanf("%d %d", &n, &m);
    for(int i = 0; i < n; i++)scanf("%d", a+i), b[i]=a[i];
    sort(b, b+n);
    int *pn = unique(b, b+n);
    L_LIMIT = 0, R_LIMIT = pn-b-1;
    for(int i = 0; i < n; i++)add(i+1, lower_bound(b, pn, a[i])-b);
    while(m--)
    {
        int l, r, k;scanf("%d %d %d", &l, &r, &k);
        printf("%d\n", b[kth(l, r, k)]);
    }
    return 0;
}