mayoko’s diary

プロコンとかいろいろ。

POJ 2104 K-th Number

実は蟻本の平方分割のところから読んでなかったので読んでます。

解法

蟻本通り。ただ B = 1000 だと TLE して, 900 だと通りました。

const int MAXN = 100010;
const int B = 900;
int N, M;
int A[MAXN];
int nums[MAXN];
vector<int> bucket[MAXN/B];

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];
        bucket[i/B].push_back(A[i]);
    }
    sort(nums, nums+N);
    for (int i = 0; i < N/B; i++) {
        sort(bucket[i].begin(), bucket[i].end());
    }
    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 = (high+low) / 2;
            int x = nums[med];
            int tl = l, tr = r, c = 0;
            while (tl < tr && tl%B != 0) if (A[tl++] <= x) c++;
            while (tl < tr && tr%B != 0) if (A[--tr] <= x) c++;

            while (tl < tr) {
                int b = tl/B;
                c += upper_bound(bucket[b].begin(), bucket[b].end(), x) - bucket[b].begin();
                tl += B;
            }
            if (c >= k) high = med;
            else low = med;
        }
        printf("%d\n", nums[high]);
    }
    return 0;
}