CF 1968 F. Equal XOR Segments (*1800) 思维
题意：
给你一个长度为 \(n\) 的数组，如何可以把数组分成 \(k(k>1)\) 组，并且使得每组的异或和相等，那么这个数组就是完美的。现在给你 \(q\) 组询问，每次给你 \(l,r\) 。请你判断 \(a_l\) 到 \(a_r\) 之间是否是完美的。
思路：
对于每次询问，不妨我们令 \(a_l \oplus a_{l+1} \oplus... \oplus a_{r-1} \oplus a_r=S\)。
显然如果 \(S=0\) ，那么我们一定可以分成两组。
接着考虑 \(S!=0\) 的情况，首先一定只能分成奇数组，并且每组的异或和都为 \(S\), 那么我们只用考虑能否分成三组即可。因为其他组数的情况，我们都可以通过合并来变成三组的情况。
首先，我们需要维护一下前缀异或和，并且维护每个前缀异或和值出现的所有位置。(可以开一个map套vector即可，这个东西真的超级好用)。接下来我们只需要在对应的vector中二分找到对应位置即可。判断一下边界即可。
代码：
#include<bits/stdc++.h>using namespace std;#define ff first
#define ss second
#define pb push_back
#define all(u) u.begin(), u.end()
#define endl '\n'
#define debug(x) cout<<#x<<":"<<x<<endl;typedef pair<int, int> PII;
typedef long long LL;
const int inf = 0x3f3f3f3f;
const int N = 1e5 + 10, M = 105;
const int mod = 1e9 + 7;
const int cases = 1;void Showball(){int n,q;cin>>n>>q;vector<int> a(n+1),s(n+1);for(int i=1;i<=n;i++){cin>>a[i];s[i]=s[i-1]^a[i];}map<int,vector<int>> mp;for(int i=0;i<=n;i++) mp[s[i]].pb(i);while(q--){int l,r;cin>>l>>r;int S=s[r]^s[l-1];if(!S){cout<<"YES\n";continue;}auto it=lower_bound(all(mp[S^s[l-1]]),l);if(it==mp[S^s[l-1]].end()||*it>=r){cout<<"NO\n";continue;}int p=*it;it=lower_bound(all(mp[S^s[p]]),p+1);if(it==mp[S^s[p]].end()||*it>=r){cout<<"NO\n";continue;}int q=*it;cout<<(s[r]^s[q]==S?"YES\n":"NO\n"); }cout<<endl;
}
int main(){ios::sync_with_stdio(false);cin.tie(nullptr);cout.tie(nullptr);int T=1;if(cases) cin>>T;while(T--)Showball();return 0;
}
