异或 $a$ 和 $b$ 等价于异或一次 $a,b$ 的异或和，所以对排列的异或操作最多一次
易知交换次数等于排列的逆序对数
题目转化为把排列的每个数异或上一个数 $x$ ，使得排列的逆序对数最少，并求出最少的逆序对数
对于两个正整数 $a,b$
$a,b$ 记二进制上从高位到低位第一个不同的位为第 $k$ 位
若 $ a_k=1 $ 则 $ a>b $ ,反之 $ b>a $
记 $c[k][0] 为 x_k=0$ ，最高不同位为 $k$ 的数对其产生的逆序对数
记 $c[k][1] 为 x_k=1$ ，最高不同位为 $k$ 的数对其产生的正序对数
则有两种情况
$l=log_2 n$
1.不进行异或操作
$ans= \sum_{i=0}^l c[i][0]$
2.进行异或操作
$ans=1+\sum_{i=0}^l min(c[i][0],c[i][1])$
1 #include<cstdio> 2 #include<vector> 3 using namespace std; 4 #define ll long long 5 const ll maxn=1e5+5; 6 ll n,l,c[30][2],ans,res; 7 vector <ll> a; 8 void get(vector <ll> a,ll b){ 9 if(b<0||a.size()<=1)return; 10 vector <ll> oe; 11 vector <ll> zo; 12 ll o=0,z=0; 13 for(ll i:a){ 14 if((i>>b)&1){ 15 c[b][1]+=z; 16 o++; 17 oe.push_back(i); 18 } 19 else{ 20 c[b][0]+=o; 21 z++; 22 zo.push_back(i); 23 } 24 } 25 get(oe,b-1); 26 get(zo,b-1); 27 } 28 int main(){ 29 scanf("%lld",&n); 30 for(ll i=1;i<=n;i++){ 31 ll x; 32 scanf("%lld",&x); 33 a.push_back(x); 34 } 35 while((1<<l)<n)l++; 36 l--; 37 get(a,l); 38 for(ll i=0;i<=l;i++){ 39 res=res+min(c[i][0],c[i][1]); 40 ans+=c[i][0]; 41 } 42 res++; 43 printf("%lld",min(res,ans)); 44 return 0; 45 }