首先考虑直接暴力,很明显暴力算法需要每次查询里在区间内找两个合法点,时间复杂度为O(n^3),必超时,但也能过一半数据,OI赛制暴力还是香。
然后来考虑优化,看到这题第一反应是区间DP,因为子区间如果能找到合法解的话当前区间也必然能找到合法解,且区间状态与区间内部断点无关,使用区间DP能将时间复杂度控制到O(n^2) (应该是?没直接写不太清楚),但本题数据量到了1e5,O(n^2)也必然超时,所以我们应该需要一个O(n)或者O(nlogn)复杂度的算法来解决这题。
查询每组答案本身就会有O(n)的复杂度,因此留给查询的复杂度只有O(1)或者O(logn),现在留给我们的选择就不多了,同时不能用排序打乱顺序使用二分,那我的直觉就只有哈希或者线段树的查询了。
确定了大概方向我们来考虑如何去优化:
对于区间内ai ^ aj == x,由异或的运算性质可知ai ^ x == aj,
也就是说问题可以转化为看给定的区间内是否存在某一个ai,它对x的异或也在这个区间内。
那我们可以先预处理出所有ai的异或bi,但依然无法解决我们的问题,这时候我们需要找到一个转化的方向。我们寻找的本质是找序列中ai后的区间中是否存在一个bi,同时还要看这个bi的位置是否在给定的区间内部,那么也就是说,我们要去找ai后第一个bi的位置ci(不存在则放在序列末尾后一个位置),并比较bi位置和区间右端点的位置看bi是否在区间内。我们接着这个思路去看,那么是不是给定区间内的每一个ai都会有一个对应的位置ci,使得ai ^ a[ci] == x,那我们是不是只要看区间内ci的最小值就能确定是否成立了。
至此我们终于找到了突破口:查询区间最小值,现在终于轮到我们线段树登场了!现在我们终于能够将查询的时间复杂度控制在O(logn)了!这题直接拿下了!
才怪,我们现在虽然解决了查询问题,但别忘了,我们在推导中有一步需要对每一个ai找ci,我们直接实现这一步的时候会发现这一步的时间复杂度达到了O(n^2),超时了!(所以不要半场开香槟),那我们需要怎么去优化呢?
我们注意到每一次都是去找ai后的数是否满足条件,那我们可以倒序来遍历,并在每个数出现后记录该数出现的位置,这样我们每次更新遇到满足条件的数时我们记录的值永远是这个数出现的最小位置,至此,这个问题终于结束了!好耶!
也许你不太能理解最后一步的倒序遍历,我们换一个情况来看,假设我们要找到一个序列a中ai后第一个f(ai)(f是一个映射)出现的位置,那我们可以倒序遍历,并用一个哈希表b存储现在遍历到的ai的位置:即b[ai] = i,现在我们遍历到了一个新的数aj,且f(aj) = ai,那我们只需要在b中看b[f(aj)]即可,若b[f(aj)]不为0则b中的数即为它其后第一个f(ai)的位置。
用代码写出来就是这样:
const int N = 1e5;
int a[N], b[N], c[N];
int n;
void init() {
// 设f(ai) = 2 * ai
for (int i = n; i >= 1; i--) {
if (!b[2 * a[i]]) c[i] = n + 1; //ai后不存在aj使得aj == 2 * ai
else c[i] = b[2 * a[i]];
b[a[i]] = i;
}
}
下面是这题的完整代码
#include <iostream>
using namespace std;
const int N = 1e5 + 10, M = 2e6 + 5;
struct node{
int l, r;
int m;
}tr[4 * N];
int a[N], b[M],c[N], n, m, x;
void pushup(int u) {
tr[u].m = min(tr[u << 1].m, tr[u << 1 | 1].m);
}
void build(int u, int l, int r) {
if (l == r)tr[u] = { l,r,c[l] };
else {
tr[u] = { l,r};
int mid = l + r >> 1;
build(u << 1, l, mid);
build(u << 1 | 1, mid + 1, r);
pushup(u);
}
}
int query(int u, int l, int r) {
if (tr[u].l >= l && tr[u].r <= r)return tr[u].m;
int mid = tr[u].l + tr[u].r >> 1;
int res = n + 1;
if (l <= mid)res = query(u << 1, l, r);
if (r > mid)res = min(res, query(u << 1 | 1, l, r));
return res;
}
int main()
{
ios::sync_with_stdio(false);
cin.tie(0);
cin >> n >> m >> x;
for (int i = 1; i <= n; i++)
cin >> a[i];
for (int i = n; i >= 1; i--) {
if (!b[a[i] ^ x]) c[i] = n + 1;
else c[i] = b[a[i] ^ x];
b[a[i]] = i;
}
build(1, 1, n);
while (m--) {
int l, r;
cin >> l >> r;
int mi = query(1, l, r);
if (r >= mi)
cout << "yes\n";
else cout << "no\n";
}
return 0;
}