HDU 2665 Kth number (主席树)

矫情吗；* 2021-11-22 17:58 261阅读 0赞

题目链接：https://vjudge.net/contest/313769\#problem/A

![ContractedBlock.gif][] ![ExpandedBlockStart.gif][]

#include <cmath>
    #include <cstdio>
    #include <algorithm>
    #include <iostream>
    #include <cstring>
    #include <ctype.h>
    #include <map>
    #include <vector>
    #include <set>
    #include <bitset>
    #define lson rt << 1, l, mid
    #define rson rt << 1 | 1, mid + 1, r
    using namespace std;
    static const int MAX_N = 1e5 + 5;
    vector<int>vec;
    struct Node{
        int l, r, sum;
    }T[MAX_N * 20];
    int root[MAX_N], a[MAX_N], cnt, n;
    int getId(int x){
         return lower_bound(vec.begin(), vec.end(), x) - vec.begin() + 1;}  //二分查找
    void update(int l, int r, int &x, int y, int pos){
        T[++cnt] = T[y], T[cnt].sum++, x = cnt;
        if(l == r) return ;
        int mid = l + r >> 1;
        if(pos <= mid) update(l, mid, T[x].l, T[y].l, pos);
        else update(mid + 1, r, T[x].r, T[x].r, pos);
    }
    int query(int l, int r, int x, int y, int k){
        if(l == r) return l;
        int mid = l + r >> 1;
        int sum = T[T[y].l].sum - T[T[x].l].sum;
        if(sum >= k) return query(l, mid, T[x].l, T[y].l, k);
        else return query(mid + 1, r, T[x].r, T[y].r, k - sum);
    }
    void prework(){
        cnt = 0;
        vec.clear();
    }
    int main(){
    //    freopen("input.txt", "r", stdin);
    //    freopen("output.txt", "w", stdout);
        int t;
        scanf("%d", &t);
        while(t--){
            prework();
            int m;
            scanf("%d%d", &n, &m);
            for(int i = 1; i <= n; ++i) scanf("%d", &a[i]), vec.push_back(a[i]);
            sort(vec.begin(), vec.end()), vec.erase(unique(vec.begin(), vec.end()), vec.end());//离散化
            for(int i = 1; i <= n; ++i) update(1, n, root[i], root[i - 1], getId(a[i]));
            while(m--){
                int ql, qr, k;
                scanf("%d%d%d", &ql, &qr, &k);
                printf("%d\n", vec[query(1, n, root[ql - 1], root[qr], k) - 1]);
            }
        }
        return 0;
    }

转载于:https://www.cnblogs.com/xorxor/p/11236919.html

[ContractedBlock.gif]: https://images.cnblogs.com/OutliningIndicators/ContractedBlock.gif
[ExpandedBlockStart.gif]: /images/20211122/7ab7941cfc944d3a8ade760e6f90be74.png