题目链接：HDU6621-K-th Closest Distance

题意：

给一个长度为n的序列和m个询问，每次询问一个区间[l,r]内，第k小的|a[i]-p|的值。

题解：

二分答案+主席树（真没想到二分答案=-=

二分一个答案，然后检查区间[p-mid,p+mid]中有没有恰好k个数即可，用主席树检查。

参考代码：

#include <bits/stdc++.h>
using namespace std;
const int MAXN = 1e5 + 5;
const int MAXM = 1e6 + 6;
int T;
int n, m;
int a[MAXN], b[MAXN];
int rt, tot;
int Tree[MAXN], sum[MAXN * 55], ls[MAXN * 55], rs[MAXN * 55];
void build(int l, int r, int &rt)
{
    rt = ++tot;
    sum[rt] = 0;
    if (l == r)
        return;
    int mid = (l + r) >> 1;
    build(l, mid, ls[rt]);
    build(mid + 1, r, rs[rt]);
}
void update(int las, int val, int l, int r, int &rt)
{
    rt = ++tot;
    ls[rt] = ls[las];
    rs[rt] = rs[las];
    sum[rt] = sum[las] + 1;
    if (l == r)
        return;
    int mid = (l + r) >> 1;
    if (val <= mid)
        update(ls[las], val, l, mid, ls[rt]);
    else
        update(rs[las], val, mid + 1, r, rs[rt]);
}
int query(int L, int R, int l, int r, int lt, int rt)
{
    if (L <= l && r <= R)
    {
        return sum[rt] - sum[lt];
    }
    int mid = (l + r) / 2;
    int res = 0;
    if (L <= mid)
        res += query(L, R, l, mid, ls[lt], ls[rt]);
    if (R > mid)
        res += query(L, R, mid + 1, r, rs[lt], rs[rt]);
    return res;
}
int main()
{
    scanf("%d", &T);
    while (T--)
    {
        scanf("%d%d", &n, &m);
        int N = MAXM;
        tot = 0;
        build(1, n, Tree[0]);
        for (int i = 1; i <= n; i++)
        {
            scanf("%d", &a[i]);
            update(Tree[i - 1], a[i], 1, N, Tree[i]);
        }
        int prex = 0;
        while (m--)
        {
            int l, r, p, k;
            scanf("%d%d%d%d", &l, &r, &p, &k);
            l ^= prex, r ^= prex, p ^= prex, k ^= prex;
            int ll = 0, rr = N;
            while (ll <rr)
            {
                int mid = (ll + rr) / 2;
                if (query(max(1, p - mid), min(N, p + mid), 1, N, Tree[l - 1], Tree[r]) >= k)
                {
                    prex = mid;
                    rr = mid;
                }
                else
                    ll = mid + 1;
            }
            printf("%d\n", prex);
        }
    }
    return 0;
}