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.
InputThe 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).OutputFor 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
SOLUTION:
值的范围只有1e6，其实是不用离散的但是我离散了，出发点就错了
考虑没有离散，其实二分也是很很好想到的
CODE:
#include<stdio.h>
#include<string.h>
#include<algorithm>
#include<iostream>
#include<queue>
#include<math.h>
using namespace std;
#define sc(x) scanf("%d",&(x))
int n,m;
const int N = 1e6+10;
int a[N],b[N];
#define rep(i,a,b) for(int i=a;i<=b;i++)
int root[N];
vector<int> v,ans;
int tr[N*40];int tot;
int ls[N*40],rs[N*40];
void bd(int y,int &x,int l,int r,int p)
{
x=++tot; tr[x]=tr[y]+1;ls[x]=ls[y];rs[x]=rs[y];
if(l==r)return ; int mid=l+r>>1;
if(p<=mid)bd(ls[y],ls[x],l,mid,p);
else bd(rs[y],rs[x],mid+1,r,p);
}
int que(int y,int x,int l,int r,int L,int R)
{
if(L<=l&&r<=R)return tr[x]-tr[y];
int mid=l+r>>1;
int res=0;if(L<=mid)res+=que(ls[y],ls[x],l,mid,L,R);
if(R>mid)res+=que(rs[y],rs[x],mid+1,r,L,R);
return res;
}
int main()
{
int T;cin>>T;
while(T--)
{
sc(n);sc(m); v.clear(); tot=0;
memset(tr,0,sizeof tr);
memset(ls,0,sizeof ls);
memset(rs,0,sizeof rs);
rep(i,1,n)sc(a[i]);
rep(i,1,n)
bd(root[i-1],root[i],1,1e6,a[i]);
//cout<<que(root[2],root[n],1,1e6,1,4);
int ans=0;
while(m--)
{
int l,r,p,k;sc(l);sc(r);sc(p);sc(k);
l^=ans,r^=ans,p^=ans,k^=ans;
l=max(1,l);
r=min(n,r);
int ll=0,rr=5e6;
while(ll<=rr)
{
int mid=ll+rr>>1;
int sum=que(root[l-1],root[r],1,1e6,p-mid,p+mid);
if(sum>=k)rr=mid-1,ans=mid;
else ll=mid+1;
}
cout<<ans<<endl;
}
}
}
/*
1
5 1
31 2 5 45 4
1 5 100 5
2 5 3 2
*/