记录编号	442401	评测结果	AAAAAAAAAA
题目名称	[河南省队2012] 找第k小的数	最终得分	100
用户昵称	HeHe	是否通过	通过
代码语言	C++	运行时间	1.277 s
提交时间	2017-08-27 07:56:24	内存使用	1.71 MiB

#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;

inline char getc(void) { 
    static char buf[1 << 18], *fs, *ft;
    return (fs == ft && (ft = (fs = buf) + fread(buf, 1, 1 << 18, stdin)), fs == ft) ? EOF : *fs++;
}

inline int read(void) { 
    register int res = 0;
    register char tmp = getc();
    register bool f = true;
    while(!isgraph(tmp)) tmp = getc();
    if(tmp == '-') f = false, tmp = getc();
    while(isdigit(tmp))
        res = ((res + (res << 2)) << 1) + (tmp ^ 0x30),
        tmp = getc();
    if(f) return res;
    return ~res + 1;
}

#define MAXN 100010

struct NODE{ 
    int sum;
    NODE *ls, *rs;

    NODE() { 
        sum = 0;
        ls = rs = NULL;
    }
};

inline int search(int k);
NODE *Build(int l, int r);
NODE *change(NODE *pre, int k, int L, int R);
int Query(NODE *s, NODE *t, int k, int L, int R);

NODE *roots[MAXN];
int N, M, n = 1;
int a[MAXN], oa[MAXN];

int main() { 
#ifndef LOCAL
    freopen("kth.in", "r", stdin);
    freopen("kth.out", "w", stdout);
#endif
    N = read(), M = read();
    for(register int i = 1, *b = a, *ob = oa; i <= N; ++i) *(++b) = *(++ob) = read();
    sort(oa + 1, oa + 1 + N);
    for(register int i = 2, *ob1 = oa + 1, *ob2 = oa + 2; i <= N; ++i, ++ob2) if(*ob2 ^ *(ob2 - 1)) *(++ob1) = *ob2, ++n;
    //for(int i = 1; i <= n; ++i) printf("%d ", oa[i]);
    //printf("\n");
    for(register int i = 1, *b = a + 1; i <= N; ++i, ++b) *b = search(*b);
    //for(int i = 1; i <= N; ++i) printf("%d ", a[i]);
    //printf("\n");
    *roots = Build(1, n);
    NODE **c = roots;
    for(register int i = 1, *b = a + 1; i <= N; ++i, ++c) *(c + 1) = change(*c, *(b++), 1, n);

    for(int i = 1, l, r, k; i <= M; ++i) { 
        l = read(), r = read(), k = read();
        printf("%d\n", oa[Query(roots[l - 1], roots[r], k, 1, n)]);
    }

    return 0;
}

inline int search(int k) { 
    static int *x = oa, *s = oa + 1, *t = oa + 1 + n;
    return lower_bound(s, t, k) - x;
}

NODE *Build(int l, int r) { 
    NODE *p = new NODE();
    if(l ^ r) { 
        int mid = (l + r) >> 1;
        p->ls = Build(l, mid);
        p->rs = Build(mid + 1, r);
    }
    return p;
}

NODE *change(NODE *pre, int k, int L, int R) { 
    NODE *p = new NODE();
    p->sum = pre->sum + 1;
    if(L ^ R) { 
        int mid = (L + R) >> 1;
        if(k <= mid) p->rs = pre->rs, p->ls = change(pre->ls, k, L, mid);
        else p->ls = pre->ls, p->rs = change(pre->rs, k, mid + 1, R);
    }
    return p;
}

int Query(NODE *s, NODE *t, int k, int L, int R) { 
    if(L == R) return L;
    int n = t->ls->sum - s->ls->sum;
    int mid = (L + R) >> 1;
    if(k <= n) return Query(s->ls, t->ls, k, L, mid);
    else return Query(s->rs, t->rs, k - n, mid + 1, R);
}