题目大意
??给你一个n个数的序列,你可以给他们异或上一个x,求一个最小的x使得异或之后序列的逆序对最少。
解题思路
??把所有的数字都插入字典树中,并且插入的每个节点都存一下插入的下标,那么对于一个节点来说,如果只有一个分支,那么挂在这个点上的所有数字从根到这个点为止数值都是一样的,那么就不存在逆序对,否则如果有两个分支,那么就会有一部分数字大于另一部分,我们不妨枚举0的那一边数字,如果这一边的数字的下标比1的那一边要大的话,肯定就是存在逆序对的。递归处理就能算出对于每一个二进制位来说,这一位取0和取1分别会得到的逆序对数量,由于字典树的性质,挂在一个点的数字更高的二进制位都是一样的,所以没有后效性。
代码
const int maxn = 3e5+10;
int tr[maxn*31][2], idx;
ll cnt[31][2];
vector<int> ct[maxn*31];
void insert(int x, int pos) {
int p = 0;
for (int i = 30; i>=0; --i) {
int t = x>>i&1;
if (!tr[p][t]) tr[p][t] = ++idx;
p = tr[p][t];
ct[p].push_back(pos);
}
}
void dfs(int x, int p) {
if (x==-1) return;
int ls = tr[p][0], rs = tr[p][1], id = 0;
if (!ls && !rs) return;
ll sum = 0;
for (auto v : ct[ls]) {
while(id<ct[rs].size() && v>ct[rs][id]) ++id;
sum += id;
}
cnt[x][0] += sum;
cnt[x][1] += 1LL*ct[ls].size()*ct[rs].size()-sum;
//cout << x << ‘ ‘ << cnt[x][0] << ‘ ‘ << cnt[x][1] << endl;
if (ls) dfs(x-1, ls);
if (rs) dfs(x-1, rs);
}
int main() {
IOS;
int n; cin >> n;
for (int i = 1, num; i<=n; ++i) {
cin >> num;
insert(num, i);
}
dfs(30, 0);
ll ans = 0, val = 0;
for (int i = 30; i>=0; --i) {
if (cnt[i][0]<=cnt[i][1]) ans += cnt[i][0];
else {
ans += cnt[i][1];
val ^= (1<<i);
}
}
cout << ans << ‘ ‘ << val << endl;
return 0;
}