K-th Closest Distance

Posted on | Post modified:

K-th Closest Distance(主席树+二分)

题面

题意：

一个长度为$n$的数组，有$m$次查询，对于每次查询，查询$[l,r]$内距离$p$第$k$近的距离。强制在线。

思路

考虑二分距离$dis$，对于每次的$dis$，判断在$[l,r]$内在区间$[p-dis,p+dis]$内的数是否超过了$k$个，该操作可以利用主席树来实现，复杂度$O(n \cdot log(n)^2$。

代码:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
#include<bits/stdc++.h>

using namespace std;
const int N = 1e6+100;
struct node{
    int l,r,num;
}T[N*3];
vector<int> v;
int n,m,cnt,roots[N],a[N],k,L,R,P,id[N];
void update(int l, int r, int &x, int y, int p) {
    T[++cnt]=T[y];T[cnt].num++;x=cnt;
    if (l == r) return ;
    int mid = l + r >> 1;
    if (p <= mid)  update(l, mid, T[x].l,T[y].l,p);
    else update( mid + 1, r,T[x].r,T[y].r,p);
}
int all;
void query(int l,int r,int nl,int nr,int x,int y){
    if(all>=k) return ;
    if(nl<=l&&r<=nr){
        all+=T[y].num-T[x].num;
        return ;
    }
    int mid=(l+r)>>1;
    if(nl<=mid) query(l,mid,nl,nr,T[x].l,T[y].l);
    if(nr>mid) query(mid+1,r,nl,nr,T[x].r,T[y].r);
}
bool check(int dis){
    all=0;
    int l=lower_bound(a+1,a+n+1,P-dis)-a;
    int r=upper_bound(a+1,a+n+1,P+dis)-a-1;
    query(1,n,L,R,roots[l-1],roots[r]);
    return all>=k;
}
void solve(){
    int ans=0;v.clear();cnt=0;
    scanf("%d %d",&n,&m);
    for(int i=1;i<=n;i++) scanf("%d",&a[i]),id[i] = i;;
    sort(id + 1, id + n + 1, [](int i, int j) { return a[i] < a[j]; });
    sort(a+1,a+n+1);
    for(int i=1;i<=n;i++) update(1,n,roots[i],roots[i-1],id[i]);
    while(m--){
        scanf("%d %d %d %d",&L,&R,&P,&k);
        L^=ans,R^=ans,P^=ans,k^=ans;    
        long long nowl=-1,nowr=2000000000;
        while(nowr-nowl>1){
            long long mid=(nowl+nowr)>>1;
            if(check(mid)) nowr=mid;
            else nowl=mid;
        }
        ans=nowr;
        printf("%lld\n",nowr);
    }
}
int main(){
    int T;
    scanf("%d",&T);
    while(T--) solve();
    return 0;
}