題解：CF1968F（Equal XOR Segments）

題目翻譯：定義一個序列是好，當且僅當可以將其分成大于 $1$ 份，使得每個部分的異或和相等。現(xiàn)在給定一個長度為 $n$ 的序列 $a$，以及 $q$ 次查詢，每次查詢中，詢問序列 $a$ 的第 $l$ 到 $r$ 位是不是好的。（$n\le 2?10^5$ 并且 $q\le 2?10^5$）
第一步，要縮小范圍。我們不難發(fā)現(xiàn)這個段數(shù)要么是 $2$，要么是 $3$，如果有多于 $4$ 段，那么將其中任意三段合并，根據(jù)異或的性質可以證明對最終結果沒有影響，這樣一直合并，一直將段數(shù)減少 $2$，早晚能變成 $2$ 或 $3$ 段。

第二步，考慮如何求答案。如果詢問道一段區(qū)間異或起來（用前綴異或和 $s$ 維護）為 $0$，那么一定可以分成兩段；否則也就是難點——分成三段的情況。那么就相當于找到兩個數(shù) $x$ 和 $y$（$l<x<y<r$）使得 $s_x?s_{l?1}=s_y?s_x=s_r?s_y$。這個式子就等價于找到 $s_y=s_{l?1}$ 以及 $s_x=s_r$。那么我們用一個 map<int, vector<int>> 存儲某一個數(shù)在 $s$ 中出現(xiàn)在哪些位置，然后用 upper_bound 和 lower_bound 二分求出能否找到合理的 $x$ 和 $y$ 并且保證 $x<y$。比如說，我們在等于 $s_{l?1}$ 的 vector 里面找到小于 $r$ 最大的 $y$，在等于 $s_r$ 的 vector 里面找到大于 $l$ 里最小的 $x$，判斷，如果 $l<x<y<r$ 就可以，否則就不行。

具體見代碼。

#include <bits/stdc++.h>
#define N 220000
using namespace std;
int t, n, q, a[N], l, r;
int s[N];
map<int, set<int>> id;
int main() {scanf("%d", &t);while (t--) {id.clear();scanf("%d%d", &n, &q);for (int i = 1; i <= n; i++) {scanf("%d", &a[i]);s[i] = s[i - 1] ^ a[i];if (id.find(s[i]) == id.end()) {id[s[i]] = {i};} else {id[s[i]].insert(i);}}for (int i = 1; i <= q; i++) {scanf("%d%d", &l, &r);if ((s[r] ^ s[l - 1]) == 0) {printf("Yes\n");} else {auto u = id[s[l - 1]].upper_bound(r - 1);if (u == id[s[l - 1]].begin()) {printf("No\n");} else {u--;auto v = id[s[r]].lower_bound(l);if (v != id[s[r]].end() && l <= *v && *v < *u && *u < r) {printf("Yes\n");} else {printf("No\n");}}}}}return 0;
}