You have an array: a1, a2, ......, an and you must answer for some queries.
For each query, you are given an interval [L, R] and two numbers p and K. Your goal is to find the Kth closest distance between p and aL, aL+1, ..., aR.
The distance between p and ai is equal to |p - ai|.
For example:

A = {31, 2, 5, 45, 4 } and L = 2, R = 5, p = 3, K = 2.
|p - a2| = 1, |p - a3| = 2, |p - a4| = 42, |p - a5| = 1.
Sorted distance is {1, 1, 2, 42}. Thus, the 2nd closest distance is 1.

链接🔗

「HDU 6621」 K-th Closest Distance

题解

查询可以转换成, 给定pp,求最小xx,使得在区间[L,R][L,R]区间内，数值范围在[p−x,p+x][p-x,p+x]之间的数不小于kk个
然后区间小于某数的数量可以用主席树实现,然后套上一个二分即可

代码

#include <cstdio>
#include <algorithm>
#include <cstring>
using namespace std;
const int maxd = 1e6+10;
const int mx = 1e6+10;
int root[maxd],ls[maxd<<5],rs[maxd<<5],size[maxd<<5],tot,arr[maxd];
void insert(int &rt,int last,int l,int r,int v)
{
    rt = ++tot; ls[rt] = ls[last],rs[rt] = rs[last],size[rt] = size[last]+1;
    if(l==r) return;
    int mid = (l+r)>>1;
    if(v<=mid) insert(ls[rt],ls[last],l,mid,v);
    else insert(rs[rt],rs[last],mid+1,r,v);
}
int query(int x,int y,int l,int r,int v)
{
    if(!v) return 0;
    //printf("%d %d %d %d %d\n",l,r,v,size[x],size[y]);
    if(l==r) return size[y] - size[x];
    int mid = (l+r)>>1;
    if(v <= mid) return query(ls[x],ls[y],l,mid,v);
    else return size[ls[y]] - size[ls[x]] + query(rs[x],rs[y],mid+1,r,v);
}
int main()
{
    // freopen("a.in","r",stdin);
    // freopen("k.out","w",stdout);
    int t,n,m,flag;scanf("%d",&t);
    while(t--)
    {
        scanf("%d %d",&n,&m);
        root[0] = 0;tot =0; flag = 0;
        for(int i=1;i<=n;i++) scanf("%d",&arr[i]);
        for(int i=1;i<=n;i++) insert(root[i],root[i-1],1,mx,arr[i]);
        for(int i=1;i<=m;i++)
        {
            int x,y,p,k;
            scanf("%d %d %d %d",&x,&y,&p,&k);
            x^=flag,y^=flag,p^=flag,k^=flag;
            int l=0,r=1e6,ans;
            while(l<=r)
            {
                int mid = (l+r)>>1;
                int ll = max(1,p-mid);
                int rr = min(maxd,p+mid);
                int now = query(root[x-1],root[y],1,mx,rr) - query(root[x-1],root[y],1,mx,ll-1);
                //printf("%d %d %d %d\n",ll,rr,query(root[x-1],root[y],1,mx,rr) ,query(root[x-1],root[y],1,mx,ll-1));
                if(now >= k) ans = mid,r = mid-1;
                else l = mid+1;
            }
            flag =ans;
            printf("%d\n",ans);
        }
        //printf("%d\n",query(root[0],root[5],1,mx,5)-query(root[0],root[5],1,mx,4));
    }
    return 0;
}