记录编号	154802	评测结果	AAAAAAAAAA
题目名称	[NEERC 2004] K小数	最终得分	100
用户昵称	OEE_ZFF	是否通过	通过
代码语言	C++	运行时间	0.004 s
提交时间	2015-03-25 00:34:52	内存使用	24.35 MiB

#include <algorithm>
#include <cstdio>
#include <iostream>

using namespace std;

int A[100001], Sorted[100001];
unsigned Root[100001], tot;

struct NODE
{
    unsigned hen, tai, num;
}   Tree[2000000];

inline unsigned build(const unsigned hen, const unsigned tai, const unsigned temp)
{
    const unsigned now = ++tot;
    Tree[now].hen = hen;
    Tree[now].tai = tai;
    Tree[now].num = temp;
    return now;
}

inline void amend(unsigned &now, const unsigned last, const unsigned hen, const unsigned tai, const unsigned temp)
{
    now = build(Tree[last].hen, Tree[last].tai, Tree[last].num + 1);
    if (hen == tai) return;
    const unsigned shinshi = (hen + tai) / 2;
    if (temp <= shinshi) amend(Tree[now].hen, Tree[last].hen, hen, shinshi, temp);
        else amend(Tree[now].tai, Tree[last].tai, shinshi + 1, tai, temp);
}

inline unsigned ask(const unsigned west, const unsigned east, const unsigned hen, const unsigned tai, const unsigned temp)
{
    if (hen == tai) return hen;
    const unsigned shinshi = (hen + tai) / 2, num = Tree[Tree[east].hen].num - Tree[Tree[west].hen].num;
    if (temp <= num) return ask(Tree[west].hen, Tree[east].hen, hen, shinshi, temp);
        else return ask(Tree[west].tai, Tree[east].tai, shinshi + 1, tai, temp - num);
}

int main(void)
{
    freopen("kthnumber.in", "r", stdin);
    freopen("kthnumber.out", "w", stdout);
    unsigned i, j, k, m, n, num;
    cin >> n >> m;
    for (i = 1; i <= n; ++i)
    {
        scanf("%d", &A[i]);
        Sorted[i] = A[i];
    }
    sort(Sorted + 1, Sorted + n + 1);
    num = unique(Sorted + 1, Sorted + n + 1) - (Sorted + 1);
    for (i = 1; i <= n; ++i) amend(Root[i], Root[i - 1], 1, num, lower_bound(Sorted + 1, Sorted + num + 1, A[i]) - Sorted);
    for (; m; --m)
    {
        scanf("%u%u%u", &i, &j, &k);
        printf("%d\n", Sorted[ask(Root[i - 1], Root[j], 1, num, k)]);
    }
    fclose(stdin);
    fclose(stdout);
    return 0;
}