POJ 2104 K-th Number その 2

蟻本に書いてあるから別に解説は書きませんがとりあえずメモ。

問題

2104 -- K-th Number

解法

はい。

const int ST_SIZE = (1<<18)-1;
const int MAXN = 100010;
int N, M;
int A[MAXN];
int nums[MAXN];
vector<int> dat[ST_SIZE];


void init(int k, int l, int r) {
    if (r-l == 1) {
        dat[k].push_back(A[l]);
    } else {
        int lch = 2*k+1, rch = 2*k+2;
        init(lch, l, (l+r)/2);
        init(rch, (l+r)/2, r);
        dat[k].resize(r-l);
        merge(dat[lch].begin(), dat[lch].end(), dat[rch].begin(), dat[rch].end(), dat[k].begin());
    }
}

int query(int i, int j, int x, int k, int l, int r) {
    if (j <= l || r <= i) return 0;
    if (i <= l && r <= j) return upper_bound(dat[k].begin(), dat[k].end(), x) - dat[k].begin();
    int lch = query(i, j, x, 2*k+1, l, (l+r)/2);
    int rch = query(i, j, x, 2*k+2, (l+r)/2, r);
    return lch+rch;
}

int main() {
    scanf("%d %d", &N, &M);
    for (int i = 0; i < N; i++) scanf("%d", A+i);
    for (int i = 0; i < N; i++) nums[i] = A[i];
    sort(nums, nums+N);
    init(0, 0, N);
    while (M--) {
        int l, r, k;
        scanf("%d %d %d", &l, &r, &k);
        l--;
        int low = -1, high = N-1;
        while (high - low > 1) {
            int med = (low+high) / 2;
            int x = nums[med];
            int tmp = query(l, r, x, 0, 0, N);
            if (tmp >= k) high = med;
            else low = med;
        }
        printf("%d\n", nums[high]);
    }
    return 0;
}