题意：求一个最小的x，使x与数组a每一个元素异或后，逆序对数最小。
思路：二进制下，考虑数的高位对数值的大小影响更大，我们从最高位开始，如果这一位上异或1比异或0的逆序数对更小，那么最终答案的这一位就应该为1，否则为0。（最开始每一位上用树状数组求逆序对，然后T12了，看题解才知道需要用字典树，wao //0 1序列异或1后，正序对数=之前的逆序数对，逆序对数=之前的正序数对
1、因为数的高位能直接接决定数值的大小，在当前位异或1并不能改变高位相同的这些数内部的逆序数对，所以我们处理时可以不用考虑整个数的大小，只需要看高位的逆序对数是否能通过异或1变得更小 2、同样的道理，当 当前位的前几位数确定且前几位不同时，改变当前位也不能改变这两个数的相对大小。所以我们只用计算每组相同高位的数内部的逆序数对和正序数对，看是否需要异或1。这就需要用到字典树了。
#include<algorithm> #include<iostream> #include<cstdio> #include<cstring> #include<map> #include<set> #include<queue> #include<vector> using namespace std; #define LL long long #define uLL unsigned long long #define PII pair<int,int> #define mid ((l + r)>>1) #define chl (root<<1) #define chr (root<<1|1) #define lowbit(x) ( x&(-x) ) const int manx = 5e6 + 10; const int INF = 2e9; const int mod = 1e4+7; int n,tree[manx<<1][2],a,root,cou=1,siz[manx<<1]; LL dp[35][2];//dp[][0]dp[][1]分别代表每组相同高位的数 内部的逆序数对和 和 正序数和 void iinsert(int x) { root=0; for(int i=30;i>=0;i--){ int net=(x&(1<<i))?1:0; dp[i][net]+=siz[tree[root][net^1]]; //因为按顺序插入字典树，所以： //当前位为1，正序数对+=高位相同时，当前位为0的数的个数 //当前位为0，逆序数对+=高位相同时，当前位为1的数的个数 if(!tree[root][net]) tree[root][net]=cou++; root=tree[root][net]; siz[root]++; } } int main() { int ans=0; LL sum=0; scanf("%d",&n); memset(dp,0,sizeof dp); memset(siz,0,sizeof siz); for(int i=1;i<=n;i++){ scanf("%d",&a); iinsert(a); } for(int i=30;i>=0;i--){ if(dp[i][0]>dp[i][1]){//逆序对数和>正序对数和 ans|=(1<<i); sum+=dp[i][1]; } else sum+=dp[i][0]; } printf("%lld %d\n",sum,ans); return 0; }