NTUJ 1707 k-th number

恩沒錯，就是傳說中的經典的劃分樹。                                                                                                           .




其實超級好寫，只是兒子的區間要算好|||。

還有如果數字相同要處理一下，這個有點麻煩就是，還好這題保證沒有相同

網路上找得到許多教程，其實瞪著notonlysuccess的圖看幾秒就會領悟了

所以只是來備份代碼


#include <cstdio>
#include <cstring>
#include <algorithm>

#define MN 100010

int sorted[MN], val[20][MN], lcnt[20][MN];
int N, Q;

void build(int tl, int tr, int dep) {
    if(tl == tr) return ;
    int mid = (tl+tr)/2, pre = 0;
    int lc = tl, rc = mid+1;
    for(int i=tl; i<=tr; i++) {
        lcnt[dep][i] = pre;
        if(val[dep][i] <= sorted[mid]) {
            lcnt[dep][i] ++;
            val[dep+1][lc ++] = val[dep][i];
        }
        else val[dep+1][rc ++] = val[dep][i];
        pre = lcnt[dep][i];
    }
    build(tl, mid, dep+1);
    build(mid+1, tr, dep+1);
}

int query(int ql, int qr, int tl, int tr, int k, int dep) {
    if(tl == tr) return val[dep][tl];
    int mid = (tl+tr)/2, ql2L, qr2L, qinL;
    ql2L = lcnt[dep][ql] - (val[dep][ql]<=sorted[mid]);
    qr2L = lcnt[dep][qr];
    qinL = qr2L - ql2L;
    int newL, newR, newK;
    if(qinL >= k) {
        newL = tl + ql2L;
        newR = tl + qr2L - 1;
        newK = k;
        return query(newL, newR, tl, mid, newK, dep+1);
    }
    else {
        newL = mid + ql - tl - ql2L + 1;
        newR = mid + qr - tl - qr2L + 1;
        newK = k - qinL;
        return query(newL, newR, mid+1, tr, newK, dep+1);
    }

}

int main() {
    while(~scanf("%d%d", &N, &Q)) {
        for(int i=1; i<=N; i++) {
            scanf("%d", sorted+i);
            val[0][i] = sorted[i];
        }
        std::sort(sorted+1, sorted+1+N);
        build(1, N, 0);
        for(int i=1; i<=Q; i++) {
            int L, R, K;
            scanf("%d%d%d", &L, &R, &K);
            printf("%d\n", query(L, R, 1, N, K, 0));
        }
    }
}