思路： 考虑按这个数组建立01字典树，那么在插入每个数的时候，逆序对的产生会发生在：这一位是0，且1的那个兄弟节点有已经插入的数 的时候。 那么我们可以在建树的时候算出逆序对的个数。 建完树之后，我们要贪心的选择x的每个二进制位选0还是1，因为对于字典树来说，每个节点的两个子树的逆序对是不会被祖先节点的0/1影响的，那么我们先找到每一位放0/1的时候逆序对的个数。这样就能贪心的找到每一位放什么更优了，期间逆序对的个数也可以顺便算出来。
#pragma GCC optimize(2) #pragma GCC optimize(3) #include <bits/stdc++.h> using namespace std; typedef long long LL; const int N = 3e5 + 10; #define fi first #define se second #define pb push_back #define wzh(x) cerr<<#x<<'='<<x<<endl; int n,a[N]; int root=1,cnt=1; int sz[N*31]; LL dif[N*31]; int t[N*31][2]; void insert(int now,int x){ for(int i=30;i>=0;i--){ bool st=1<<i&x; if(!st)dif[now]+=sz[t[now][!st]]; if(!t[now][st])t[now][st]=++cnt; sz[t[now][st]]++; now=t[now][st]; } } LL gan,can[33][2]; int ans; void gao(int now,int dep){ //cout<<now<<' '<<dep<<endl; int l=sz[t[now][0]],r=sz[t[now][1]]; LL di=1ll*l*r-dif[now]; // 1 0 //di 反 0 1 //dif 正 1 0 can[dep][0]+=dif[now]; can[dep][1]+=di; if(t[now][0])gao(t[now][0],dep-1); if(t[now][1])gao(t[now][1],dep-1); } int b[N]; int T[N]; void add(int x,int y){ for(;x<N;x+=x&-x)T[x]+=y; } int get(int x){ int y=0; for(;x;x-=x&-x)y+=T[x]; return y; } int main() { ios::sync_with_stdio(false); cin>>n; for(int i=1;i<=n;i++) { cin >> a[i]; insert(root,a[i]); } gao(1,30); for(int i=30;i>=0;i--){ if(can[i][0]>can[i][1])ans+=1<<i,gan+=can[i][1]; else gan+=can[i][0]; } cout<<gan<<' '<<ans<<'\n'; return 0; }