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

题意：

给你一个数组，q次询问，每次问你[l,r]范围内与p距离第k大的元素的与p的距离，强制在线

思路：

主席树提取出[l,r]内的权值线段树，然后二分与p的距离mid

ask该权值线段树里[p-mid,p+mid]的数的个数，使其刚好大于等于k

代码：

#include<iostream>

#include<cstdio>

#include<algorithm>

#include<cmath>

#include<cstring>

#include<string>

#include<stack>

#include<queue>

#include<deque>

#include<set>

#include<vector>

#include<map>

#define fst first

#define sc second

#define pb push_back

#define mem(a,b) memset(a,b,sizeof(a))

#define lson l,mid,root<<1

#define rson mid+1,r,root<<1|1

#define lc root<<1

#define rc root<<1|1

using namespace std;

typedef double db;

typedef long double ldb;

typedef long long ll;

typedef unsigned long long ull;

typedef pair<int,int> PI;

typedef pair<ll,ll> PLL;

const db eps = 1e-;

const int mod = 1e9+;

const int maxn = 2e7+2e6+;

const int maxm = 4e6+;

const int inf = 0x3f3f3f3f;

const db pi = acos(-1.0);

int ls[maxn],rs[maxn],dat[maxn];

int tot;

int n,q;

int a[maxm];

int root[maxm];

int t;

int insert(int now, int l, int r, int x, int val){

    int p = ++tot;

    ls[p]=ls[now];rs[p]=rs[now];dat[p]=dat[now];

    if(l==r){

        dat[p]+=val;

        return p;

    }

    int mid = (l+r)>>;

    if(x<=mid)ls[p]=insert(ls[now],l,mid,x,val);

    else rs[p]=insert(rs[now],mid+,r,x,val);

    dat[p]=dat[ls[p]]+dat[rs[p]];

    return p;

}

int ask(int lst, int now, int l, int r, int L, int R){

    //printf("%d %d %d %d %d %d\n",lst,now,l,r,L,R);

    int mid = (l+r)>>;

    int ans = ;

    if(L<=l&&r<=R)return dat[now]-dat[lst];

    if(L<=mid)ans+=ask(ls[lst],ls[now],l,mid,L,R);

    if(mid<R)ans+=ask(rs[lst],rs[now],mid+,r,L,R);

    return ans;

}

int K,p;

bool cmp(int a, int b){

    return abs(a-p)<abs(b-p);

}

int main(){

    scanf("%d", &t);

    while(t--){

        int lstans = ;

        mem(dat,);

        tot=;

        scanf("%d %d", &n, &q);

        for(int i = ; i <= n; i++){

            scanf("%d", &a[i]);

            root[i]=insert(root[i-],,,a[i],);

        }

        while(q--){

            int l, r;

            scanf("%d %d %d %d", &l, &r, &p, &K);

            l^=lstans;

            r^=lstans;

            p^=lstans;

            K^=lstans;

            int ans;

            int L = ;

            int R = ;

            while(L<=R){

                int mid = (L+R)>>;

                int res = ask(root[l-],root[r],,,max(,p-mid),min(,p+mid));

                if(res>=K){

                    ans=mid;

                    R=mid-;

                }

                else L=mid+;

            }

            lstans=ans;

            printf("%d\n",ans);

        }

    }

    return ;

}

/*

1

5 2

31 2 5 45 4

1 5 5 1

2 5 3 2

 */