HDU-6621 K-th Closs Distance(主席ツリー+2分)

You have an array:a 1,a 2,,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-a 2|=1、124; p-a 3|=2、124; p-a 4𞓜=42、124; p-a 5|=1.  Sorted distance is{1,1,2,42}.Thus,the 2 nd 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 a 1,a 2,…,an(1<=ai==10^6).Each value of array is unique.  Each of the next m lineas 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 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

                    主席の木を作って、それから毎回距離を調べて二点でいいです.PS(この問題に注意して、毎回l、r、p、kは前回の答えに対して異議を唱えます.waは一年経って、これはちょっと得られないので、本当に嫌です.)

#include
using namespace std;
const int maxn = 100005;
const int M = maxn * 30;
int n, q, tot, m;
int a[maxn], t[maxn];
int T[maxn], lson[M], rson[M], c[M];
void Init_hash() {
	for (int i = 1; i <= n; i++)
		t[i] = a[i];
	sort(t + 1, t + 1 + n);
	m = unique(t + 1, t + 1 + n) - t - 1;
}
int build(int l, int r) {
	int root = tot++;
	c[root] = 0;
	if (l != r) {
		int mid = (l + r) >> 1;
		lson[root] = build(l, mid);
		rson[root] = build(mid + 1, r);
	}
	return root;
}
int update(int root, int pos, int val) {
	int newroot = tot++, tmp = newroot;
	c[newroot] = c[root] + val;
	int l = 1, r = m;
	while (l < r) {
		int mid = (l + r) >> 1;
		if (pos <= mid) {
			lson[newroot] = tot++; rson[newroot] = rson[root];
			newroot = lson[newroot]; root = lson[root];
			r = mid;
		}
		else {
			rson[newroot] = tot++; lson[newroot] = lson[root];
			newroot = rson[newroot]; root = rson[root];
			l = mid + 1;
		}
		c[newroot] = c[root] + val;
	}
	return tmp;
}
int Hash(int x) {
	return lower_bound(t + 1, t + 1 + m, x) - t;
}
int query(int left_root, int right_root, int l, int r, int L, int R) {
	if (L <= t[l] && t[r] <= R) {
		return  c[right_root] - c[left_root];
	}
	int mid = (l + r) >> 1, sum = 0;
	if (L <= t[mid]) {
		sum += query(lson[left_root], lson[right_root], l, mid, L, R);
	}
	if (R >= t[mid + 1]) {
		sum += query(rson[left_root], rson[right_root], mid + 1, r, L, R);
	}
	return sum;
}
int main() {
	int te; scanf("%d", &te);
	while (te--) {
		scanf("%d%d", &n, &q);
		tot = 0;
		for (int i = 1; i <= n; i++)
			scanf("%d", &a[i]);
		Init_hash();
		T[0] = build(1, m);
		for (int i = 1; i <= n; i++) {
			int pos = Hash(a[i]);
			T[i] = update(T[i - 1], pos, 1);
		}

		int re = 0;
		while (q--) {
			int l, r, k, p;
			scanf("%d%d%d%d", &l, &r, &p, &k);
			l ^= re; r ^= re; p ^= re; k ^= re;
			int li = 0, ri = 1000005, ans = -1;
			while (li <= ri) {
				int mid = (li + ri) >> 1;
				int limit = p - mid, rimit = p + mid;
				int res = query(T[l - 1], T[r], 1, m, limit, rimit);
				if (res >= k) {
					ans = mid;
					ri = mid - 1;
				}
				else li = mid + 1;
			}
			printf("%d
", ans);
			re = ans;
		}
	}
	return 0;
}