POJ 2104

题目大意

暂无

题目解法

暂无

RTFC

#include <algorithm>
#include <cstdio>
#include <cstring>
const int N = int(1e5 + 5);
int n, a[N], b[N], idx, rt[N];
struct node
{
    int ch[2], sz;
} T[N * 20];
void insert(int y, int &x, int l, int r, int p)
{
    T[x = ++idx] = T[y];
    T[x].sz++;
    if (l == r - 1) return;
    int m = (l + r) >> 1;
    p < m ?
        insert(T[y].ch[0], T[x].ch[0], l, m, p) :
        insert(T[y].ch[1], T[x].ch[1], m, r, p);
}
int query(int nl, int nr, int l, int r, int k)
{
    if (l == r - 1) return l;
    int delta = T[T[nr].ch[0]].sz - T[T[nl].ch[0]].sz, m = (l + r) >> 1;
    return delta >= k ?
        query(T[nl].ch[0], T[nr].ch[0], l, m, k) :
        query(T[nl].ch[1], T[nr].ch[1], m, r, k - delta);
}
int main()
{
    int q;
    scanf("%d%d", &n, &q);
    for (int i = 1; i <= n; i++) scanf("%d", a + i);
    memcpy(b, a + 1, n << 2);
    std::sort(b, b + n);
    int m = int(std::unique(b, b + n) - b);
    for (int i = 1; i <= n; i++)
        a[i] = int(std::lower_bound(b, b + m, a[i]) - b);
    for (int i = 1; i <= n; i++) insert(rt[i - 1], rt[i], 0, m, a[i]);
    while (q--)
    {
        int l, r, k;
        scanf("%d%d%d", &l, &r, &k);
        printf("%d\n", b[query(rt[l - 1], rt[r], 0, m, k)]);
    }
    return 0;
}