POJ2104 K-th Number

$n$ 个数 $m$ 次询问区间 $[l,r]$​ 第 $k$ 小值

1
#include <iostream>
2
#include <cstdio>
3
#include <algorithm>
4
using namespace std;
5
const int N = 1E5 + 7;
6
int sorted[N];
7
int t[20][N], toLeft[20][N];
8
void build(int dep, int l, int r){
9
    if(l == r) return;
10
    int mid = (l + r) >> 1;
11
    int sup = mid - l + 1;
12
    for(int i = l; i <= r; i++){
13
        if(t[dep][i] < sorted[mid]) sup--;
14
    }
15
    int sl = l, sr = mid + 1;
16
    for(int i = l; i <= r; i++){
17
        if(i == l) toLeft[dep][i] = 0;
18
        else toLeft[dep][i] = toLeft[dep][i - 1];
19
        if(t[dep][i] < sorted[mid] || (t[dep][i] == sorted[mid] && sup > 0)){
20
            toLeft[dep][i]++;
21
            t[dep + 1][sl++] = t[dep][i];
22
            if(t[dep][i] == sorted[mid]) sup--;
23
        }
24
        else t[dep + 1][sr++] = t[dep][i];
25
    }
26
    build(dep + 1, l, mid); build(dep + 1, mid + 1, r);
27
}
28
int query(int dep, int l, int r, int ql, int qr, int k){
29
    if(l == r) return t[dep][l];
30
    int mid = (l + r) >> 1;
31
    int le, qtl;
32
    le = (ql == l)?0:toLeft[dep][ql - 1];
33
    qtl = toLeft[dep][qr] - le;
34
    if(k <= qtl) return query(dep + 1, l, mid, l + le, l + le + qtl - 1, k);
35
    else return query(dep + 1, mid + 1, r, mid + ql - l - le + 1, mid + qr - l - le - qtl + 1, k - qtl);
36
}
37
int main(){
38
    int n, m, l, r, k;
39
    scanf("%d%d", &n, &m);
40
    for(int i = 1; i <= n; i++) scanf("%d", &t[0][i]), sorted[i] = t[0][i];
41
    sort(sorted + 1, sorted + n + 1);
42
    build(0, 1, n);
43
    for(int i = 1; i <= m; i++){
44
        scanf("%d%d%d", &l, &r, &k);
45
        printf("%d\n", query(0, 1, n, l, r, k));
46
    }
47
    return 0;
48
}