K-th Closest Distance HDU - 6621（第k小绝对值+主席树+二分）

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
现在才写这篇博客有点晚了。当时做这道题的时候还不太会，现在想想大体上可以想明白了。
这种第k大或者第k小的问题就是主席树。但是这次是绝对值第k小，这就很懵逼。。我们二分去找答案，二分到一个值之后，在[0,1000000]这个区间里去看[p-mid,p+mid]这个区间内有多少个值，要是个数小于k说明需要扩大范围，要是大于k的话，就需要减少范围。但是要是等于k，也要去减少范围，因为我们需要去更精确这个值。
代码如下：

#include<bits/stdc++.h> #define ll long long using namespace std;const int maxx=1e5+100; struct node{int l;int r;int num; }p[maxx<<5]; int a[maxx],root[maxx]; int n,m,tot;inline int read() {char ch = getchar(); int x = 0, f = 1;while(ch < '0' || ch > '9') {if(ch == '-') f = -1;ch = getchar();} while('0' <= ch && ch <= '9') {x = x * 10 + ch - '0';ch = getchar();} return x * f; } inline int build(int l,int r) {int cur=++tot;p[cur].num=0;if(l==r) return cur;int mid=l+r>>1;p[cur].l=build(l,mid);p[cur].r=build(mid+1,r);return cur; } inline int update(int rot,int l,int r,int pos) {int cur=++tot;p[cur]=p[rot];p[cur].num++;if(l==r) return cur;int mid=l+r>>1;if(pos<=mid) p[cur].l=update(p[rot].l,l,mid,pos);else p[cur].r=update(p[rot].r,mid+1,r,pos);return cur; } inline int query(int l,int r,int L,int R,int lrot,int rrot) {if(l<=L&&R<=r) return p[rrot].num-p[lrot].num;int mid=L+R>>1;int ret=0;if(l<=mid) ret+=query(l,r,L,mid,p[lrot].l,p[rrot].l);if(r>mid) ret+=query(l,r,mid+1,R,p[lrot].r,p[rrot].r);return ret; } int main() {int t,l,r,p,k;int ans;t=read();while(t--){tot=0;n=read(),m=read();for(int i=1;i<=n;i++) a[i]=read();//root[0]=build(1,1000000);for(int i=1;i<=n;i++) root[i]=update(root[i-1],1,1000000,a[i]);ans=0;while(m--){l=read(),r=read(),p=read(),k=read();l^=ans;r^=ans;p^=ans;k^=ans;int li=0,ri=1000000;while(li<=ri){int mid=li+ri>>1;if(query(max(1,p-mid),min(1000000,p+mid),1,1000000,root[l-1],root[r])>=k) {ri=mid-1;ans=mid;}else li=mid+1;}printf("%d\n",ans);}}return 0; }

快速读入优化后只需要3000+ms，有时候读入优化真的很管用。。
努力加油a啊，(^o)/~

总结

以上是生活随笔为你收集整理的K-th Closest Distance HDU - 6621（第k小绝对值+主席树+二分）的全部内容，希望文章能够帮你解决所遇到的问题。

如果觉得生活随笔网站内容还不错，欢迎将生活随笔推荐给好友。