提交时间:2024-11-05 19:45:57

运行 ID: 34309

#include<bits/stdc++.h> #define ll long long #define i128 __int128_t using namespace std; const int N=2e5+10,mod=998244353; struct dsu{ int fa[N],siz[N]; int fd(int x){ if(x==fa[x]) return x; return fa[x]=fd(fa[x]); }void mg(int x,int y){ x=fd(x),y=fd(y); if(x==y) return ; if(siz[x]>siz[y]) swap(x,y); fa[x]=y;siz[y]+=siz[x]; } }dsu; int n;int a[N],b[N]; bool vis[N]; int main(){ cin>>n; for(int i=1;i<=n;i++) cin>>a[i]; for(int i=1;i<=n;i++) cin>>b[i]; for(int i=1;i<=n;i++) a[n+1]^=a[i],b[n+1]^=b[i]; map<int,int> q; for(int i=1;i<=n+1;i++) q[a[i]]=1,q[b[i]]=1; int tp=0; for(auto &ed:q) ed.second=++tp; for(int i=1;i<=n+1;i++) a[i]=q[a[i]],b[i]=q[b[i]]; for(int i=1;i<=tp;i++) dsu.fa[i]=i,dsu.siz[i]=1; int ans=0; for(int i=1;i<=n+1;i++){ if(a[i]!=b[i]||(i==n+1)){ dsu.mg(a[i],b[i]);ans++;//cout<<i<<' '; //cout<<a[i]<<' '<<b[i]<<' '<<i<<' '<<tp<<endl; } }for(int i=1;i<=tp;i++){ int rt=dsu.fd(i);//cout<<rt<<' '; if(dsu.siz[rt]==1) continue; if(!vis[rt]){ vis[rt]=1;ans++; } }if(dsu.siz[dsu.fd(b[n+1])]!=1) ans-=2; cout<<ans; return 0; }