poj 2104 K-th Number

题解

区间第k大
主席树裸题

https://blog.csdn.net/CillyB/article/details/75912440

#include <iostream>
#include <cstdio>
#include <algorithm>
const int N = 1e5 + 10;
int n, m, cnt;
int Root[N], rank[N], Lson[N * 20], Rson[N * 20], W[N * 20];
struct Node {
    int x, id;
    bool operator <(Node a) const {return x < a.x;}
} data[N];
void Fill(int x, int y) {Lson[x] = Lson[y], Rson[x] = Rson[y], W[x] = W[y];}
void Update(int num, int &rt, int l, int r) {
    Fill(++ cnt, rt);
    rt = cnt;
    W[rt] ++;
    if(l == r) return ;
    int mid = (l + r) >> 1;
    if(num <= mid) Update(num, Lson[rt], l, mid);
    else Update(num, Rson[rt], mid + 1, r);
}
int Ans;
void Ask(int i, int j, int k, int l, int r) {
    int del = W[Lson[j]] - W[Lson[i]];
    if(l == r) {Ans = l; return ;}
    int mid = (l + r) >> 1;
    if(k <= del) Ask(Lson[i], Lson[j], k, l, mid);
    else Ask(Rson[i], Rson[j], k - del, mid + 1, r);
}
int main() {
    std:: cin >> n >> m;
    for(int i = 1; i <= n; i ++) {std:: cin >> data[i].x; data[i].id = i;}
    std:: sort(data + 1, data + n + 1);
    for(int i = 1; i <= n; i ++) rank[data[i].id] = i;
    for(int i = 1; i <= n; i ++) {
        Root[i] = Root[i - 1];
        Update(rank[i], Root[i], 1, n);
    }
    for(int i = 1; i <= m; i ++) {
        int l, r, k;
        std:: cin >> l >> r >> k;
        Ask(Root[l - 1], Root[r], k, 1, n);
        std:: cout << data[Ans].x << "\n";
    }
    return 0;
}