K-th Closest Distance（主席树 + 二分）

水深无声 2021-11-10 01:02 289阅读 0赞

Problem Description  
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.

Input  
The first line of the input contains an integer T (1 <= T <= 3) denoting the number of test cases.  
For each test case:  
冘The first line contains two integers n and m (1 <= n, m <= 10^5) denoting the size of array and number of queries.  
The second line contains n space-separated integers a1, a2, …, an (1 <= ai <= 10^6). Each value of array is unique.  
Each of the next m lines contains four integers L’, R’, p’ and K’.  
From these 4 numbers, you must get a real query L, R, p, K like this:  
L = L’ xor X, R = R’ xor X, p = p’ xor X, K = K’ xor X, where X is just previous answer and at the beginning, X = 0.  
(1 <= L < R <= n, 1 <= p <= 10^6, 1 <= K <= 169, R - L + 1 >= K).

Output  
For each query print a single line containing the Kth closest distance between p and aL, aL+1, …, aR.  
Sample Input  
1  
5 2  
31 2 5 45 4  
1 5 5 1  
2 5 3 2  
Sample Output

0  
1

分析：  
其实这个题，我真的思路全会了，可是还是wa了一个晚上。  
这个题目就是主席树+二分。  
题目范围都可以不离散化。但是我还是离散了一下。

主席树就很正常的按模板建。二分那个差值mid，那么当前需要查询的区间就是p-mid，p+mid。同时，在真正查询的时候，我们要把数值通过lower\_bound转换成b里面的下标进行查询。

#include"stdio.h"
    #include"string.h"
    #include"algorithm"
    using namespace std;
    
    int N,M;
    int T[200010],L[50 * 200010],R[50 * 200010],sum[50 * 200010],top;
    int a[200010],b[200010],len;
    
    void Build_Tree(int &root,int l,int r)
    {
        root = ++ top;
        sum[root] = 0;
        int mid = (l + r) >> 1;
        if(l < r)
        {
            Build_Tree(L[root],l,mid);
            Build_Tree(R[root],mid + 1,r);
        }
    }
    
    void Update(int &root,int root1,int l,int r,int x)
    {
        root = ++ top;
        L[root] = L[root1];
        R[root] = R[root1];
        sum[root] = sum[root1] + 1;
        int mid = (l + r) >> 1;
        if(l >= r)
            return ;
        if(x > mid)
            Update(R[root],R[root1],mid + 1,r,x);
        else
            Update(L[root],L[root1],l,mid,x);
    }
    
    int query(int x,int y,int ql,int qr,int l,int r)
    {
        if(ql <= l && qr >= r) return sum[y] - sum[x];
        int mid = (l + r) >> 1;
        int res = 0;
        if(ql <= mid)
            res += query(L[x],L[y],ql,qr,l,mid);
        if(qr > mid)
            res += query(R[x],R[y],ql,qr,mid + 1,r);
        return res;
    }
    
    int check(int ql,int qr,int l,int r,int k)
    {
        int t1 = lower_bound(b + 1,b + 1 + len,ql) - b;
        int t2 = lower_bound(b + 1,b + 1 + len,qr + 1) - b - 1;
        if(t1 > len || t2 > len || t1 > t2) return 0;
        int tmp = query(T[l - 1],T[r],t1,t2,1,len);
        if(tmp >= k) return 1;
        return 0;
    }
    
    int main()
    {
        int t;
        scanf("%d",&t);
        while(t --)
        {
            top = 0;
            scanf("%d%d",&N,&M);
            for(int i = 1; i <= N; i ++)
            {
                scanf("%d",&a[i]);
                b[i] = a[i];
            }
            sort(b + 1,b + 1 + N);
            len = unique(b + 1,b + 1 + N) - b - 1;
            Build_Tree(T[0],1,len);
            for(int i = 1; i <= N; i ++)
            {
                int t = lower_bound(b + 1,b + 1 + len,a[i]) - b;
                Update(T[i],T[i - 1],1,len,t);
            }
    
            int x = 0;
            while(M --)
            {
                int l,r,p,k;
                scanf("%d%d%d%d",&l,&r,&p,&k);
                l ^= x;  r ^= x; p ^= x; k ^= x;
    
                int l1 = 0,r1 = 1e6;
                while(l1 + 1 < r1)
                {
                    int mid = (l1 + r1) >> 1;
                    if(check(p - mid,p + mid,l,r,k) == 1)
                        r1 = mid;
                    else
                        l1 = mid;
                }
                if(check(p - l1,p + l1,l,r,k) == 1)
                    x = l1;
                else
                    x = r1;
                printf("%d\n",x);
            }
        }
    }