题意：
给出一个数组，询问最小的数x，使得数组里每个数异或这个x后，整个数组的逆序对数量最少。
题解：
/* *题意： *给出一个数组，询问一个最小的值x，使得这个数组的所有元素异或x后逆序对最少 *考虑贪心做法，从低位到高位构造x *每次比较x的第i位是1和x的第i位是0所形成的数组的逆序对数量，选择少的那一个 *可以将每个数的二进制形式高位到低位存到一个字典树里 *两个数的大小取决于他们二进制位上第一个不同的位 *可以单独考虑字典树的其中一个子树，设它的左子树为l，右子树为r，那么l里面的所有数一定是比r小的 *可以枚举l里面有多少数的下标比r里面的数的下标小，这样一个子树内的逆序对数量就统计完了 *然后将所有子树以此合并，最后根节点得到的是所有逆序数的数量 *接下来考虑贪心构造x的这个过程 *假设当前贪心到x的第i位，这一位是1，那么对应层数的子树要反转 *开一个dp数组分别统计翻转和不翻转的逆序对数量 *就完成了这个贪心的过程 */ #include<bits/stdc++.h> using namespace std; const int maxn=4e6+100; typedef long long ll; int n,Trie[maxn][2],tot; ll dp[maxn][2]; vector<int> g[maxn]; void add (int x,int p) { int u=0; for (int i=29;i>=0;i--) { int bit=((x>>i)&1); if (!Trie[u][bit]) Trie[u][bit]=++tot; u=Trie[u][bit]; g[u].push_back(p); } } void dfs (int u,int dep) { if (Trie[u][0]) dfs(Trie[u][0],dep-1); if (Trie[u][1]) dfs(Trie[u][1],dep-1); if (!Trie[u][0]||!Trie[u][1]) return; ll sum=0; int tt=0; for (int i=0;i<g[Trie[u][0]].size();i++) { while (tt<g[Trie[u][1]].size()&&g[Trie[u][1]][tt]<g[Trie[u][0]][i]) tt++; sum+=tt; } dp[dep][0]+=sum; dp[dep][1]+=(ll)g[Trie[u][0]].size()*g[Trie[u][1]].size()-sum; } void solve () { scanf("%d",&n); for (int i=1;i<=n;i++) { int x; scanf("%d",&x); add(x,i); } dfs(0,29); ll ans=0,u=0; for (int i=0;i<=29;i++) { ans+=min(dp[i][0],dp[i][1]); if (dp[i][1]<dp[i][0]) u+=(1<<i); } printf("%lld %lld ",ans,u); } int main () {solve();}