異或圖

思路：

簡單推一下：

當 l e n = 1 len=1 len=1時：

要滿足 a [ u ] ⊕ a [ v ] = k a[u]\oplus a[v]=k a[u]⊕a[v]=k

當 l e n > 1 len>1 len>1時：

e p : l e n = 2 ep:len=2 ep:len=2時

a [ u ] ⊕ a [ x ] ⊕ a [ v ] = k ⊕ a [ v ] = a [ u ] ⊕ k a[u]\oplus a[x]\oplus a[v]=k\oplus a[v]=a[u]\oplus k a[u]⊕a[x]⊕a[v]=k⊕a[v]=a[u]⊕k

→ a [ u ] = = a [ v ] , \rightarrow a[u]==a[v], →a[u]==a[v],且存在 a [ x ] = a [ u ] ⊕ k a[x]=a[u]\oplus k a[x]=a[u]⊕k

l e n > 2 len>2 len>2時

e p : l e n = 3 ep:len=3 ep:len=3

a [ u ] ⊕ a [ x ] ⊕ a [ y ] ⊕ a [ v ] = a [ u ] ⊕ k ⊕ a [ v ] = 0 → a [ u ] ⊕ a [ v ] = k a[u]\oplus a[x]\oplus a[y]\oplus a[v]=a[u]\oplus k\oplus a[v]=0\rightarrow a[u]\oplus a[v]=k a[u]⊕a[x]⊕a[y]⊕a[v]=a[u]⊕k⊕a[v]=0→a[u]⊕a[v]=k

這樣顯然可以直接用 l e n = 1 len=1 len=1。

此題的坑點是很容易逾時，要用快讀，而且牛客的評測機快讀也容易逾時，相同的代碼，我交兩遍一份 A C AC AC，一份逾時。。

#include<bits/stdc++.h>     using namespace std;     typedef long long ll;     const int N=1e6+5,M=1e6+5,inf=0x3f3f3f3f,mod=1e9+7;     #define mst(a) memset(a,0,sizeof a)     #define lx x<<1     #define rx x<<1|1     #define reg register     #define PII pair<int,int>     #define fi first     #define se second     int a[N];     inline void read(int &x){         x=0;int w=1;         char ch=getchar();         while(ch<'0'||ch>'9') {if(ch=='-') w=-1;ch=getchar();}         for(;ch>='0'&&ch<='9';ch=getchar())             x=(x<<3)+(x<<1)+(ch&15);         x*=w;     }     unordered_map<int,bool>mp;     int main(){         int n,q;         read(n),read(q);         for(int i=1,x;i<=n;i++) read(a[i]),mp[a[i]]=1;         while(q--){             int k,x,y;             read(k),read(x),read(y);             if((a[x]^a[y])==k) printf("1\n");             else if(a[x]==a[y]&&mp[a[x]^k]) printf("2\n");             else printf("-1\n");         }         return 0;     }