[agc016d]xor replace

题意：

题解：

棒棒的神仙题。。。这题只是D题？？？（myh：看题五分钟，讨论两小时）

首先这个异或和是假的，比如我现在有$a=(a_1,a_2,a_3,a_4)$，操作一下$a_2$，就变成了$a=(a_1,a_1\oplus a_2\oplus a_3\oplus a_4,a_3,a_4)$；

再操作一下$a_3$，因为$a_i\oplus a_i=0$，它就变回了$a=(a_1,a_1\oplus a_2\oplus a_3\oplus a_4,a_2,a_4)$。

所以这个操作只是第一次把一个位置变成全体的异或和，后面就是在交换两个数的位置。。。

可以考虑把多出来的这个全体异或和放到$N+1$的位置，然后就变成了一次操作是交换$1$到$N$中的一个位置的数和第$N+1$个位置的数，求要多少次操作把数组a变成数组b。

无解的情况显然：如果两个数组排序后有位置不同则必定无解，先判掉；

把数组离散化，然后对于位置$i$，若$a_i\neq b_i$则从$a_i$到$b_i$连一条边；

这样子对于每个联通块，设其大小为$S$，则必定可以用$S-1$次操作使其中的位置全部满足条件（感性理解一下？）；

在每个联通块之间，需要额外的一次操作使$N+1$的位置在两个块之间转换；

最后要特殊考虑$N+1$这个位置，如果它已经在某个联通块内则没有影响，否则要单独作为一个联通块考虑，答案++；

所以最后的答案就是边数+联通块数-1，用并查集xjb维护一下即可。

代码：

 #include<algorithm>

 #include<iostream>

 #include<cstring>

 #include<cstdio>

 #include<cmath>

 #include<queue>

 #include<map>

 #define inf 2147483647

 #define eps 1e-9

 using namespace std;

 typedef long long ll;

 int n,ans=,ta=,tb=,cnt=,fa[],a[],b[],aa[],bb[],lsh[];

 map<int,bool>mp;

 int ff(int u){

     return fa[u]==u?u:fa[u]=ff(fa[u]);

 }

 int main(){

     scanf("%d",&n);

     for(int i=;i<=n;i++){

         scanf("%d",&a[i]);

         ta^=a[i];

         aa[i]=a[i];

     }

     for(int i=;i<=n;i++){

         scanf("%d",&b[i]);

         tb^=b[i];

         bb[i]=b[i];

     }

     n++;

     a[n]=aa[n]=ta,b[n]=bb[n]=tb;

     sort(aa+,aa+n+);

     sort(bb+,bb+n+);

     for(int i=;i<n;i++){

         if(aa[i]!=bb[i])return puts("-1"),;

     }

     for(int i=;i<n;i++){

         if(a[i]!=b[i]){

             lsh[++cnt]=a[i];

             lsh[++cnt]=b[i];

             ans++;

         }

     }

     lsh[++cnt]=ta;

     lsh[++cnt]=tb;

     if(!ans)return puts(""),;

     sort(lsh+,lsh+cnt+);

     cnt=unique(lsh+,lsh+cnt+)-lsh-;

     for(int i=;i<=cnt;i++)fa[i]=i;

     for(int i=;i<=n;i++){

         if(a[i]!=b[i]){

             a[i]=lower_bound(lsh+,lsh+cnt+,a[i])-lsh;

             b[i]=lower_bound(lsh+,lsh+cnt+,b[i])-lsh;

             if(!mp[a[i]])mp[a[i]]=true;

             if(!mp[b[i]])mp[b[i]]=true;

             int f1=ff(a[i]),f2=ff(b[i]);

             fa[f1]=f2;

         }

     }

     for(int i=;i<=cnt;i++){

         if(fa[i]==i)ans++;

     }

     printf("%d",ans-);

     return ;

 }