题解：AT_abc364_d [ABC364D] K-th Nearest

· · 题解

看到“第 k 近的点的距离”，想到了二分，二分这个距离，查询在这个距离中是否有 k 个点。
形式化地说，查询操作可以表述为：设当前询问的点的坐标为 x，距离为 s，那么我们就要查询在 [x-s,x+s] 中的点的数量。如果 < k，那么距离就要扩大一点，否则距离缩小一点。
由于 -10^8 \le a_i,b_i \le 10^8，坐标范围过大，又要查询到精确区间，可以使用动态开点线段树。

#include<stdio.h>
struct sss{long long sum,ch[2];}tree[1600005];
long long n,q,s[100005],b,k,root,tot;
void insert(long long &rt,int l,int r,int whe)
{
    if(!rt) rt=++tot;
    if(l==r) {tree[rt].sum++;return;}
    int mid=(l+r)>>1;
    if(whe<=mid) insert(tree[rt].ch[0],l,mid,whe);
    else insert(tree[rt].ch[1],mid+1,r,whe);
    tree[rt].sum=tree[tree[rt].ch[0]].sum+tree[tree[rt].ch[1]].sum;
}
long long ask(long long rt,long long l,long long r,long long ll,long long rr)
{
    if(!rt) return 0;
    if(ll<1) ll=1;if(rr>200000005) rr=200000005;
    if(ll<=l&&r<=rr) return tree[rt].sum;
    if(r<ll||rr<l) return 0;
    return ask(tree[rt].ch[0],l,(l+r)>>1,ll,rr)+ask(tree[rt].ch[1],((l+r)>>1)+1,r,ll,rr);
}
int main()
{
    scanf("%lld%lld",&n,&q);
    for(int i=1;i<=n;i++) scanf("%lld",&s[i]),insert(root,1,200000005,s[i]+100000001);
    while(q--)
    {
        scanf("%lld%lld",&b,&k);
        long long l=0,r=200000005,ans;
        while(l<=r)
        {
            long long mid=(l+r)>>1;
            if(ask(root,1,200000005,b-mid+100000001,b+mid+100000001)<k) l=mid+1;
            else r=mid-1,ans=mid;
        }
        printf("%lld\n",ans);
    }
}