XOR Inverse的题解

 [这题](https://www.luogu.com.cn/problem/CF1416C)，就是一道和[这题](https://www.luogu.com.cn/problem/CF85D)一样的暴力题！       
```         
                  ——Zachary_zhong
```
# C1 题意
首先，想要A(shou)C(wan)这题，想法很简单，不就是把x从1枚举到 $2^{32}-1$ 吗，然后把整个数组都异或一遍，再统计数组中的逆序对就可以了，但复杂度 $O(2^{32}nlog_n)$ ，很显然，这是连样例都过不去的
# C2 细化
然后，我们考虑优化，发现可以把原来的 $O(2^{32}-1)$ 优化到 $O(31)$ ，就是因为可以考虑按位异或这个值，你是永远不会发现异或到后面然后又发现前面不异或是最优的，所以我们可以暴力，首先从最高位(int的最高数字位,要开long long)枚举到最低位(注意，必须是从高到低)，如果答案加上这个值更优，更新答案，否则不更新。时间复杂度 $\approx O(nlog_n)$ 大约 $5*10^8$ 左右，卡卡常直接过
# C3 Code
```c++
#include<bits/stdc++.h>
using namespace std;
#define int long long
int n,a[500009],ans,tmp[500009],b[500009];
inline int read()
{
    int x=0,f=1;
    char ch=getchar();
    while(ch<'0'||ch>'9')
    {
        if(ch=='-')
            f=-1;
        ch=getchar();
    }
    while(ch>='0' && ch<='9')
        x=x*10+ch-'0',ch=getchar();
    return x*f;
}
inline void my_sort(int l,int r)
{
    int mid=(l+r)/2,nl=l,nr=mid+1,tmpp=l;
    if(l==r) return;
    else
        my_sort(l,mid),
        my_sort(mid+1,r);
    while(nl<=mid&&nr<=r)
        if(a[nl]<=a[nr])
            tmp[tmpp++]=a[nl++];
    else
        tmp[tmpp++]=a[nr++],ans+=mid-nl+1;
    while(nl<=mid)
        tmp[tmpp++]=a[nl++];
    while(nr<=r)
        tmp[tmpp++]=a[nr++];
    for(int i=l;i<=r;i++)
        a[i]=tmp[i];
}
inline void fy()
{
    for(int i=1;i<=n;i++)
        a[i]=b[i];
}
signed main()
{
    n=read();
    for(int i=1;i<=n;i++)
        a[i]=read(),b[i]=a[i];
    int minn=INT_MAX,num=0;
    my_sort(1,n);minn=ans;
    fy();
    for(int i=31;i>=0;i--)
    {
        ans=0;num+=(1ll<<i);
        for(int j=1;j<=n;j++)
            a[j]=a[j]^num;
        my_sort(1,n);
        fy();
        if(ans<minn) minn=ans;
        else num-=(1ll<<i);
    }
    cout<<minn<<' '<<num<<endl;
    return 0;
}
```
# C4 后记
交这题的时候CF炸了，结果题目评测时一遍过，另外，这题必须卡常，我平均每个测试点有 $1500ms+$ 。