杭电多校第四场-H- K-th Closest Distance

题目描述

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.

输入

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).

输出

For each query print a single line containing the Kth closest distance between p and aL, aL+1, ..., aR.

样例输入

1

5 2

31 2 5 45 4

1 5 5 1

2 5 3 2

样例输出

0

1

题意

给一个序列A，每次询问L，R，p，k，输出[L,R]区间中第k大的|p-a[i]| 

思路

二分答案，查询[L,R]中[p-mid,p+mid]的数的个数

可以用主席树/归并树维护区间x，y之间数的个数（题解说还可以用线段树）

主席树O(mlog1e6logn) 归并树O(mlog1e6logn^)  
归并树：https://www.cnblogs.com/bennettz/p/8342242.html

#include <bits/stdc++.h>

#define ll long long

using namespace std;

const int N=1e5+;

int T,n,m;

int a[N],t[][N];

int read()

{

    int x=,f=;char ch=getchar();

    while(ch<''||ch>''){if(ch=='-')f=-;ch=getchar();}

    while(ch>=''&&ch<=''){x=x*+ch-'';ch=getchar();}

    return x*f;

}

void build(int s,int l,int r)

{

    if (l==r)

    {

        t[s][l]=a[l];

        return;

    }

    int mid=(l+r)>>;

    build(s+,l,mid); build(s+,mid+,r);

    for (int i=l,j=mid+,k=l;i<=mid||j<=r;)

    {

        if (j>r) t[s][k++]=t[s+][i++];

        else if (i>mid || t[s+][i]>t[s+][j]) t[s][k++]=t[s+][j++];

        else t[s][k++]=t[s+][i++];

    }

}

int query(int s,int l,int r,int L,int R,int x,int y)

{

    if (x>y ) return ;

    if (L<=l&r<=R)

    {

        //printf("x=%d,y=%d,l=%d,r=%d,>y=%d,>=x=%d\n",x,y,l,r,upper_bound(t[s]+l,t[s]+r+1,y),upper_bound(t[s]+l,t[s]+r+1,x));

        return upper_bound(t[s]+l,t[s]+r+,y)-lower_bound(t[s]+l,t[s]+r+,x);

    }

    int mid=(l+r)>>,ans=;

    if (L<=mid) ans+=query(s+,l,mid,L,R,x,y);

    if (R>mid) ans+=query(s+,mid+,r,L,R,x,y);

    return ans;

}

int main()

{

   // freopen("14162.in","r",stdin);

   // freopen("1.out","w",stdout);

    T=read();

    while(T--)

    {

        n=read(); m=read();

        //memset(t,0,sizeof(t));

        for (int i=;i<=n;i++) a[i]=read();

        build(,,n);

        int ans=;

        int L,R,p,k;

        while (m--)

        {

            L=read(); R=read(); p=read(); k=read();

            L^=ans; R^=ans; p^=ans; k^=ans;

            int l=,r=;

            while (l<=r)

            {

                int mid=(l+r)>>;

                //cout<<mid<<endl;

                if (query(,,n,L,R,p-mid,p+mid)>=k) ans=mid,r=mid-;

                else l=mid+;

            }

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

        }

    }

   // fclose(stdin);

   // fclose(stdout);

    return ;

}

归并树

#include <bits/stdc++.h>

using namespace std;

const int N=1e5+;

int ls[N*],rs[N*],s[N*],root[N];

int a[N],b[N];

int T,n,m,sz;

int read()

{

    int x=,f=;char ch=getchar();

    while(ch<''||ch>''){if(ch=='-')f=-;ch=getchar();}

    while(ch>=''&&ch<=''){x=x*+ch-'';ch=getchar();}

    return x*f;

}

void Insert(int l,int r,int x,int &y,int v)

{

    y=++sz;

    s[y]=s[x]+;

    if (l==r) return;

    ls[y]=ls[x]; rs[y]=rs[x];

    int mid=(l+r)>>;

    if (v<=mid) Insert(l,mid,ls[x],ls[y],v);

    else Insert(mid+,r,rs[x],rs[y],v);

}

int query(int l,int r,int L,int R,int x,int y)

{

    if (L<=l&&r<=R) return s[y]-s[x];

    int ret=;

    int mid=(l+r)>>;

    if (L<=mid) ret+=query(l,mid,L,R,ls[x],ls[y]);

    if (R>mid) ret+=query(mid+,r,L,R,rs[x],rs[y]);

    return ret;

}

int main()

{

    T=read();

    while(T--)

    {

        sz=;

        n=read(); m=read();

        for (int i=;i<=n;i++) a[i]=read(),b[i]=a[i];

        sort(b+,b++n);

        int cnt=unique(b+,b++n)-b-;

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

        {

            a[i]=lower_bound(b+,b++cnt,a[i])-b+;

            Insert(,N,root[i-],root[i],a[i]);

        }

        int ans=;

        int L,R,p,k;

        while (m--)

        {

            L=read(); R=read(); p=read(); k=read();

            L^=ans,R^=ans,p^=ans,k^=ans;

            int l=,r=;

            while (l<=r)

            {

                int mid=(l+r)>>;

                int ll=lower_bound(b+,b++cnt,p-mid)-b+;

                int rr=upper_bound(b+,b++cnt,p+mid)-b;

                if (query(,N,ll,rr,root[L-],root[R])>=k) ans=mid,r=mid-;

                else l=mid+;

            }

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

        }

    }

    return ;

}

主席树

 

杭电多校第四场-H- K-th Closest Distance的相关教程结束。