HDU2665-Kth number(主席树)

题目链接:HDU2665-Kth number

题意:

查询区间第K大的数。

题解:

主席树模板。

参考代码:

#include <bits/stdc++.h>
using namespace std;
const int MAXN = 100005;
int n, m;
int a[MAXN], b[MAXN];
int rt, tot;
int Tree[MAXN], sum[MAXN * 20], ls[MAXN * 20], rs[MAXN * 20];
void build(int l, int r, int &rt)
{
    rt = ++tot;
    sum[rt] = 0;
    if (l == r)
        return;
    int mid = (l + r) >> 1;
    build(l, mid, ls[rt]);
    build(mid + 1, r, rs[rt]);
}
void update(int las, int val, int l, int r, int &rt)
{
    rt = ++tot;
    ls[rt] = ls[las];
    rs[rt] = rs[las];
    sum[rt] = sum[las] + 1;
    if (l == r)
        return;
    int mid = (l + r) >> 1;
    if (val <= mid)
        update(ls[las], val, l, mid, ls[rt]);
    else
        update(rs[las], val, mid + 1, r, rs[rt]);
}
int query(int L, int R, int l, int r, int K)
{
    if (l == r)
        return l;
    int mid = (l + r) >> 1;
    int CNT = sum[ls[R]] - sum[ls[L]];
    if (K <= CNT)
        return query(ls[L], ls[R], l, mid, K);
    else
        return query(rs[L], rs[R], mid + 1, r, K - CNT);
}
int main()
{
    int T;
    scanf("%d", &T);
    while (T--)
    {
        scanf("%d%d", &n, &m);
        for (int i = 1; i <= n; i++)
            scanf("%d", &a[i]), b[i] = a[i];
        tot = 0;
        //离散化原数组
        sort(a + 1, a + 1 + n);
        int cnt = unique(a + 1, a + 1 + n) - (a + 1);
        build(1, cnt, Tree[0]);
        for (int i = 1; i <= n; i++)
            b[i] = lower_bound(a + 1, a + 1 + cnt, b[i]) - a;
        for (int i = 1; i <= n; i++)
            update(Tree[i - 1], b[i], 1, cnt, Tree[i]);
        while (m--)
        {
            int l, r, k;
            scanf("%d%d%d", &l, &r, &k);
            int id = query(Tree[l - 1], Tree[r], 1, cnt, k);
            printf("%d\n", a[id]);
        }
    }
    return 0;
}

发表留言

人生在世,错别字在所难免,无需纠正。