POJ 6621: K-th Closest Distance

发布时间：2020-12-15 05:31:30 所属栏目：Java 来源：网络整理

导读：K-th Closest Distance Time Limit: 20000/15000 MS (Java/Others)????Memory Limit: 524288/524288 K (Java/Others) Total Submission(s): 1697????Accepted Submission(s): 633 Problem Description You have an array: a1,a2,?,an and you must answer f

K-th Closest Distance

Time Limit: 20000/15000 MS (Java/Others)????Memory Limit: 524288/524288 K (Java/Others)
Total Submission(s): 1697????Accepted Submission(s): 633

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,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,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,aR.

Sample Input

1 5 2 31 2 5 45 4 1 5 5 1 2 5 3 2

Sample Output

0 1

杭电多校第四场...

结构：主席树 + 二分

题解：首先按照模板走，创建一颗主席树。然后更具题目意思，我先设ans就是我二分的时候要找到的答案，那么就有 | p - a _n | = ans,则有两种情况?p - a _n = ans,a _n - p = ans,那么可以确定 a _n的值域 [ p - ans,p + ans ]。

注意：主席树的数组一定要开的够大，不然就会TLE...我开的40倍就TLE了，看大佬的开的55倍，改了一下就过了。

#include <iostream>
#include <cstdio>

using namespace std;

const int maxn = 1e5+7;
const int INF = 1e6+7;

struct node {
    int l,r,s;
}tree[maxn * 55];   

int root[maxn];
int arr[maxn];  
int n,m;
int cnt;

void update(int l,int r,int pre,int &cur,int pos) {
    cur = ++cnt;
    tree[cur] = tree[pre];
    tree[cur].s++;
    if(l == r) {
        return;
    }
    int mid = (l + r) >> 1;
    if(pos <= mid) {
        update(l,mid,tree[pre].l,tree[cur].l,pos);
    } else {
        update(mid + 1,tree[pre].r,tree[cur].r,pos);
    }
}

int query(int x,int y,int l,int cur) {
    if(x <= l && r <= y) {
        return tree[cur].s - tree[pre].s;
    }
    int mid = (l + r) >> 1;
    int res = 0;
    if(x <= mid) {
        res += query(x,y,l,tree[cur].l);
    } 
    if(y > mid) {
        res += query(x,mid + 1,tree[cur].r);
    }
    return res;
}

int main() {
    int T;
    scanf("%d",&T);
    while(T--) {
        scanf("%d %d",&n,&m);
        for(int i = 1; i <= n; i++) {
            scanf("%d",&arr[i]);
            update(1,INF,root[i - 1],root[i],arr[i]);
        }
        int ans = 0;
        while(m--) {
            int l,k;
            scanf("%d %d %d %d",&l,&r,&p,&k);
            l = l ^ ans;
            r = r ^ ans;
            p = p ^ ans;
            k = k ^ ans;
            int pl = 0,pr = INF;
            while(pl <= pr) {
                int mid = (pl + pr) >> 1;
                if(query(max(1,p - mid),min(INF,p + mid),1,root[l - 1],root[r]) >= k) {      //此处的max和min是为了防止超出[0,1e6]的范围
                    ans = mid;
                    pr = mid - 1;
                } else {
                    pl = mid + 1;
                }
            }
            printf("%dn",ans);
        }
    }
    return 0;
}

（编辑：李大同）

【声明】本站内容均来自网络，其相关言论仅代表作者个人观点，不代表本站立场。若无意侵犯到您的权利，请及时与联系站长删除相关内容!