hdu6621 二分加主席树

朱雀 2021-10-23 10:17 250阅读 0赞

题目链接：http://acm.hdu.edu.cn/showproblem.php?pid=6621

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

5 2

31 2 5 45 4

1 5 5 1

2 5 3 2

Sample Output

求区间内| a\[i\]-p | 第k小的数，二分答案，查询区间\[ p-ans,p+ans \]内数的数量是否大于等于k

#include<iostream>
    #include<algorithm>
    using namespace std;
    #define ll long long
    #define Max 1000000
    #define maxn 100005
    int a[maxn],b[maxn],T[maxn<<5],L[maxn<<5],R[maxn<<5],sum[maxn<<5],tot;
    inline int update(int pre,int l,int r,int x)
    {
        int rt=++tot;
        L[rt]=L[pre];
        R[rt]=R[pre];
        sum[rt]=sum[pre]+1;
        if(l<r)
        {
            int mid=l+r>>1;
            if(x<=mid)L[rt]=update(L[pre],l,mid,x);
            else R[rt]=update(R[pre],mid+1,r,x);
        }
        return rt;
    }
    inline int query(int u,int v,int ql,int qr,int l,int r)
    {
        if(ql<=l&&qr>=r)return sum[v]-sum[u];
        int mid=l+r>>1,ans=0;
        if(ql<=mid)ans+=query(L[u],L[v],ql,qr,l,mid);
        if(qr>mid)ans+=query(R[u],R[v],ql,qr,mid+1,r);
        return ans;
    }
    int main()
    {
        int t;
        cin>>t;
        for(int W=1;W<=t;W++)
        {
            int n,m;
            cin>>n>>m;
            for(int i=1;i<=n;i++)
            {
                cin>>a[i];
            }
            T[0]=sum[0]=L[0]=R[0]=tot=0;
            for(int i=1;i<=n;i++)
            {
                T[i]=update(T[i-1],1,Max,a[i]);
            }
            int l,r,p,k,x=0;
            for(int i=1;i<=m;i++)
            {
                cin>>l>>r>>p>>k;
                l^=x;r^=x;p^=x;k^=x;
                int pl=0,pr=Max;
                while(pl<pr)
                {
                    int mid=pl+pr>>1;
                    if(query(T[l-1],T[r],max(1,p-mid),min(Max,p+mid),1,Max)>=k)
                    {
                        x=mid;
                        pr=mid;
                    }
                    else pl=mid+1;
                }
                cout<<x<<endl;
            }
        }
        return 0;
    }

转载于:https://www.cnblogs.com/chen99/p/11294015.html