P8773 题解

前言

题目传送门！

更好的阅读体验？

一道有趣的题目。

思路

对于一个数 \(a_i\)，如果有 \(a_i \oplus t = x\)，显然 \(t = a_i \oplus x\)。

设 \(loc_i\) 表示上一个 \(t\) 出现的位置。这个是很容易维护的。

那么对于一组询问 \([l, r]\)，如果存在，必然是有一个 \(l \le i \le r\) 满足 \(loc_i \ge l\)。

换种说法，\([l, r]\) 存在，当且仅当 \(\max\limits_{l \le i \le r} loc_i \ge l\)。

这玩意显然可以用线段树维护。然后就做完了。

但是也是可以用 ST 的，并且更优，但是我肯定不会再打一份代码啊。

代码

这个是模拟赛时候的代码。因为赛时降智就写了线段树，每组询问一只 \(\log\)。

#include <iostream>
#include <cstdio>
#include <cmath>
using namespace std;
int n, q, x, loc[1919810];
namespace SegmentTree {
	int mx[400005];
	#define ls pos << 1
	#define rs pos << 1 | 1
	void build(int l, int r, int pos)
	{
		if (l == r)
		{
			int a;
			scanf("%d", &a);
			loc[a] = l, mx[pos] = loc[a ^ x];			
			return;
		}
		int mid = (l + r) >> 1;
		build(l, mid, ls), build(mid + 1, r, rs);
		mx[pos] = max(mx[ls], mx[rs]);
	}
	int query(int l, int r, int pos, int L, int R)
	{
		if (L <= l && r <= R) return mx[pos];
		int mid = (l + r) >> 1, ans = 0;
		if (L <= mid) ans = max(ans, query(l, mid, ls, L, R));
		if (mid < R) ans = max(ans, query(mid + 1, r, rs, L, R));
		return ans;
	}
}; using namespace SegmentTree;

int main()
{
	scanf("%d%d%d", &n, &q, &x);
	build(1, n, 1);
	while (q--)
	{
		int l, r;
		scanf("%d%d", &l, &r);
		if (query(1, n, 1, l, r) >= l) puts("yes"); else puts("no");
	}
	return 0;
}

希望能帮助到大家！