思路：异或 T r i e + Trie+ Trie+贪心。
考虑一个性质：两个数的大小只需比较其最高位。
因此考虑将数的每位从高到低存入字典树，显然一个结点的左子树(该位为0)的数小于右子树(该位为1)。
因此我们就可以计算出每个位逆序对的贡献，然后贪心地对 x x x从高位开始枚举。
另外计算子树的大小和子树的逆序对，可以在插入结点时统计。
#include<bits/stdc++.h> using namespace std; typedef long long ll; const int N=5e6+5,M=2e4+5,inf=0x3f3f3f3f,mod=1e9+7; #define mst(a,b) memset(a,b,sizeof a) #define lx x<<1 #define rx x<<1|1 #define reg register #define PII pair<int,int> #define fi first #define se second #define pb push_back #define il inline int ch[N][2],sz[N],id,n; ll dp[30][2]; //dp[i][0]表示第i位选择1的逆序对数,dp[i][1]表示第i位选择0的逆序对数 void add(int x){ int p=0; for(int i=29;~i;i--){ int v=(x>>i)&1; if(!ch[p][v]) ch[p][v]=++id; dp[i][v^1]+=sz[ch[p][v^1]]; p=ch[p][v],sz[p]++; } } int main(){ scanf("%d",&n); for(int i=1;i<=n;i++){ int x;scanf("%d",&x);add(x); } ll cnt=0,ans=0; for(int i=29;~i;i--){ if(dp[i][0]<dp[i][1]) ans+=(1<<i),cnt+=dp[i][0]; else cnt+=dp[i][1]; } printf("%lld %lld\n",cnt,ans); return 0; }