HDU6621 K-th Closest Distance 第 k 小绝对值（主席树 + 二分）

红太狼 2021-11-13 22:04 196阅读 0赞

## 题意：给一个数组，每次给 l ,r, p, k，问区间 \[l, r\] 的数与 p 作差的绝对值的第 k 小，这个绝对值是多少。 ##

## 分析：二分答案ans，然后从主席树中查询\[p - ans, p + ans\]的区间和是否大于等于k即可。这里用的是动态开点的写法。 ##

## 代码（by许）： ##

#include<bits/stdc++.h>
    using namespace std;
    const int maxn = 1e5 + 10, N = 1e6;
    int rt[maxn], ls[maxn * 22], rs[maxn * 22], sum[maxn * 22], cnt;
    #define m (l + r) / 2
    void up(int &o, int pre, int l, int r, int k) {
        o = ++cnt;
        sum[o] = sum[pre] + 1;
        ls[o] = ls[pre];
        rs[o] = rs[pre];
        if (l == r)
            return;
        if (k <= m)
            up(ls[o], ls[pre], l, m, k);
        else
            up(rs[o], rs[pre], m + 1, r, k);
    }
    int qu(int o, int pre, int l, int r, int ql, int qr) {
        if (l >= ql && r <= qr)
            return sum[o] - sum[pre];
        int res = 0;
        if (ql <= m)
            res += qu(ls[o], ls[pre], l, m, ql, qr);
        if (qr > m)
            res += qu(rs[o], rs[pre], m + 1, r, ql, qr);
        return res;
    }
    int solve(int x, int len, int l, int r) {
        int L = max(x - len, 1);
        int R = min(x + len, N);
        return qu(rt[r], rt[l - 1], 1, N, L, R);
    }
    int main() {
        int T;
        scanf("%d", &T);
        while (T--) {
            int n, q, x, l, r, p, k, ans = 0;
            cnt = 0;
            scanf("%d%d", &n, &q);
            for (int i = 1; i <= n; i++) {
                scanf("%d", &x);
                up(rt[i], rt[i - 1], 1, N, x);
            }
            while (q--) {
                scanf("%d%d%d%d", &l, &r, &p, &k);
                l ^= ans, r ^= ans, p ^= ans, k ^= ans;
                int L = 0, R = 1e6;
                while (L < R) {
                    int mid = (L + R) / 2;
                    if (solve(p, mid, l, r) < k)
                        L = mid + 1;
                    else
                        R = mid;
                }
                printf("%d\n", ans = L);
            }
        }
        return 0;
    }