QOJ7937 题解

异或 $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])$  

#include<cstdio>
#include<vector>
using namespace std;
#define ll long long
const ll maxn=1e5+5;
ll n,l,c[30][2],ans,res;
vector <ll> a;
void get(vector <ll> a,ll b){
    if(b<0||a.size()<=1)return;
    vector <ll> oe;
    vector <ll> zo;
    ll o=0,z=0;
    for(ll i:a){
        if((i>>b)&1){
            c[b][1]+=z;
            o++;
            oe.push_back(i);
        }
        else{
            c[b][0]+=o;
            z++;
            zo.push_back(i);
        }
    }
    get(oe,b-1);
    get(zo,b-1);
}
int main(){
    scanf("%lld",&n);
    for(ll i=1;i<=n;i++){
        ll x;
        scanf("%lld",&x);
        a.push_back(x);
    }
    while((1<<l)<n)l++;
    l--;
    get(a,l);
    for(ll i=0;i<=l;i++){
        res=res+min(c[i][0],c[i][1]);
        ans+=c[i][0];
    }
    res++;
    printf("%lld",min(res,ans));
    return 0;
}