整体二分（POJ2104 静态第k大查询）

#include <iostream>
#include <string.h>
#include <stdio.h>
#include <algorithm>
#include <string>
using namespace std;

const int lim = 1e9;
int ans[200000];
int c[200000];
struct query {
    int l, r;
    int k, cnt;
    int id;
}q[200000], b[200000];

struct point {
    int x, num;
    bool operator < (const point & rhs) const {
        return x < rhs.x;
    }
}a[2000000];

int n, qu;

int lowbit(int x) { return x & (-x); }

void add(int id, int x) {
    while (id <= n) {
        c[id] += x;
        id += lowbit(id);
    }
}

int getsum(int id) {
    int res = 0;
    while (id) {
        res += c[id];
        id -= lowbit(id);
    }
    return res;
}

void solve(int L, int R, int l, int r) {
    if (L == R) {
        for (int i = l; i <= r; ++i) {
            ans[q[i].id] = L;
        }
        return;
    }
    int mid = L + R >> 1;
    int curl = l, curr = r;
    int ll = 1, rr = n + 1;
    while (ll < rr) {       //二分找出第一个大于等于L的a数组的下标 (lower_bound)
        int m = ll + rr >> 1;
        if (a[m].x >= L) {
            rr = m;
        }
        else {
            ll = m + 1;
        }
    }
    for (int i = rr; i <= n && a[i].x <= mid; ++i)  //树状数组维护 [L, mid] 之间的 a[i].x 的个数
        add(a[i].num, 1);
    for (int i = l; i <= r; ++i)            //q[i].cnt 表示在[q[i].l, q[i].r]之间的a[i].x的个数
        q[i].cnt = getsum(q[i].r) - getsum(q[i].l - 1);
    for (int i = rr; i <= n && a[i].x <= mid; ++i)   //更新完q[i].cnt 后 恢复树状数组
        add(a[i].num, -1);
    for (int i = l; i <= r; ++i) {
        if (q[i].cnt >= q[i].k) {
            b[curl++] = q[i];
        }
        else {
            q[i].k -= q[i].cnt;
            b[curr--] = q[i];
        }
    }
    for (int i = l; i <= r; ++i) {
        q[i] = b[i];
    }
    if(curl != l)
        solve(L, mid, l, curl - 1);
    if(curr != r)
        solve(mid + 1, R, curr + 1, r);
}

void test3() {
    scanf("%d%d", &n, &qu);
    for (int i = 1; i <= n; ++i) {
        scanf("%d", &a[i].x);
        a[i].num = i;
    }
    sort(a + 1, a + n + 1);
    for (int i = 1; i <= qu; ++i) {
        scanf("%d%d%d", &q[i].l, &q[i].r, &q[i].k);
        q[i].id = i;
    }
    solve(-lim, lim, 1, qu);
    for (int i = 1; i <= qu; ++i)
        printf("%d
", ans[i]);
}


int main() {
    test3();
    return 0;
}