【BZOJ 4103】【THUSC 2015】异或运算

http://www.lydsy.com/JudgeOnline/problem.php?id=4103

对长的那一维建可持久化trie树（主席树？）

最主要的思路是对短的那一维每一位暴力，每一位都记录分别匹配到了trie上的哪两个点（区间左开右闭，所以两个点）。

时间复杂度\(O(np\log m)\)。

#include<cstdio>

#include<cstring>

#include<algorithm>

using namespace std;

const int N = 300003;

struct node {int ch[2], s;} T[N * 32];

int cnt = 0, root[N], x[1003], y[N], n, m, tl[1003], tr[1003];

void update(int &pos, int num, int tmp) {

	T[++cnt] = T[pos]; pos = cnt; ++T[pos].s;

	if (tmp == -1) return;

	update(T[pos].ch[(num >> tmp) & 1], num, tmp - 1);

}

int query(int u, int d, int k, int tmp) {

	if (tmp == -1) return 0;

	if (tmp == 2) {

		++tmp; --tmp;

	}

	int s = 0, v;

	for (int i = u; i <= d; ++i) {

		v = ((x[i] >> tmp) & 1) ^ 1;

		s += T[T[tr[i]].ch[v]].s - T[T[tl[i]].ch[v]].s;

	}

	if (s >= k) {

		for (int i = u; i <= d; ++i) {

			v = ((x[i] >> tmp) & 1) ^ 1;

			tl[i] = T[tl[i]].ch[v];

			tr[i] = T[tr[i]].ch[v];

		}

		return query(u, d, k, tmp - 1) | (1 << tmp);

	} else {

		k -= s;

		for (int i = u; i <= d; ++i) {

			v = (x[i] >> tmp) & 1;

			tl[i] = T[tl[i]].ch[v];

			tr[i] = T[tr[i]].ch[v];

		}

		return query(u, d, k, tmp - 1);

	}

}

int main() {

	scanf("%d%d", &n, &m);

	for (int i = 1; i <= n; ++i) scanf("%d", x + i);

	for (int i = 1; i <= m; ++i) {

		root[i] = root[i - 1];

		scanf("%d", y + i);

		update(root[i], y[i], 30);

	}

	int p, u, d, l, r, k; scanf("%d", &p);

	while (p--) {

		scanf("%d%d%d%d%d", &u, &d, &l, &r, &k);

		for (int i = u; i <= d; ++i)

			tl[i] = root[l - 1], tr[i] = root[r];

		printf("%d\n", query(u, d, k, 30));

	}

	return 0;

}