[bzoj 2741] 【FOTILE模拟赛】L

给定一个长度为 n 的序列和 m 个询问, 求某些区间内的最大连续异或和. (n ≤ 12000, m ≤ 6000) 先求前缀和, 问题转化为在给定区间找两个数, 使异或值最大.

如果是问整个序列的答案, 可以扔一棵 Trie 树. 如果一个端点固定, 可以扔一棵可持久化 Trie 树. 现在是在区间里随便找俩数......但是数据范围很小, 考虑分块.

只需快速得到一些连续的整块的答案和它们的 Trie 树. 用可持久化 Trie 得到任意一个区间的 Trie, 再暴力预处理一下所有连续整块的答案即可.

typedef long long ll;

const int N = 12002;

struct Trie
{
	int ptr, ch[N * 33][2], v[N * 33];
	int new_node(int o)
	{
		++ptr;
		ch[ptr][0] = ch[o][0], ch[ptr][1] = ch[o][1];
		v[ptr] = v[o];
		return ptr;
	}
	void insert(int p, int& o, int x, int d)
	{
		++v[o = new_node(p)];
		if (d != -1)
		{
			int t = (x >> d) & 1;
			insert(ch[p][t], ch[o][t], x, d-1);
		}
	}
	int query(int p, int o, int x, int d)
	{
		if (d == -1) return 0;
		int t = (x >> d) & 1;
		return v[ch[o][t^1]] - v[ch[p][t^1]]
			? (1<<d) | query(ch[p][t^1], ch[o][t^1], x, d-1) : query(ch[p][t], ch[o][t], x, d-1);
	}
} T;

int a[N], buf[N], * root = buf + 1, ans[111][111], size, block;

int query(int x, int y)
{
	int l = x / size, r = y / size, ret = 0;
	if (l == r)
	{
		rep (i, x+1, y+1)
			ret = max(ret, T.query(root[x-1], root[i-1], a[i], 31));
	}
	else
	{
		ret = r-l > 1 ? ans[l+1][r-1] : 0;
		rep (i, x, (l + 1) * size)
			ret = max(ret, T.query(root[i], root[y], a[i], 31));
		rep (i, r * size, y+1)
			ret = max(ret, T.query(root[x-1], root[i-1], a[i], 31));
	}
	return ret;
}

int main()
{
	int n, m, lastans = 0;
	scanf("%d%d", &n, &m);
	size = sqrt(n), block = (n + size - 1) / size;
	rep (i, 1, n+1) scanf("%d", a+i), a[i] ^= a[i-1];

	T.insert(0, root[0], 0, 31);
	rep (i, 1, n+1) T.insert(root[i-1], root[i], a[i], 31);

	rep (i, 0, block)
	{
		int p = root[i * size - 1];
		rep (j, i, block)
		{
			if (j > i) ans[i][j] = ans[i][j-1];
			rep (k, size * j, min(size * (j + 1), n))
				ans[i][j] = max(ans[i][j], T.query(p, root[k-1], a[k], 31));
		}
	}

	rep (i, 0, m)
	{
		int x, y;
		scanf("%d%d", &x, &y);
		x = ((ll)x + lastans) % n + 1, y = ((ll)y + lastans) % n + 1;
		if (x > y) swap(x, y);
		printf("%d\n", lastans = query(x-1, y));
	}
	return 0;
}