CF 1416 C.XOR Inverse【字典树求逆序对】

XOR Inverse
思路
将一个数二进制拆位，考虑x和y谁大谁小即看第一个不相同的二进制位上两个数的大小即可。因此贪心的从高位到低位考虑，比较每一位剩余所有数<0,1>对或者<1,0>对的数量的多少判断这一位是否要对所有的数进行更改。
主要是讲述字典树求逆序对的方法：
1、将所有数插入到字典树中，并将每个数的下标插入到其所对应的每一个0，1路径上。
2、最关键的一部分：抓住性质，比较两个数大小是比较两个数第一个不相同的二进制位。那么对于一个结点来说，其左节点的数一定都是小于右节点的数。因此遍历一遍左节点中所存入的下标，同时拿另一个指针移动右节点中存入的下标。当且仅当左节点当前下标>右节点下标时，就有逆序对贡献。
代码

#include<bits/stdc++.h>
using namespace std;

typedef long long LL;
typedef pair<int, int> PII;
const int N = 3e5 + 10;
const int inf = 0x3f3f3f3f;
const int mod = 1e9 + 7;

int tr[N * 30][2], idx;
vector<int> vec[N * 30];
LL f[31][2];
int a[N];

void insert(int val, int id) {
	int p = 0;
	for(int i = 30; i >= 0; i--) {
		int x = (val >> i) & 1;
		if(!tr[p][x]) tr[p][x] = ++idx;
		p = tr[p][x];
		vec[p].push_back(id);
	}
}

void dfs(int dep, int p) {
	if(dep < 0) return;
	int l = tr[p][0], r = tr[p][1];
	LL cnt = 0, idx = 0;
	LL ls = vec[l].size(), rs = vec[r].size();
	for(int i = 0; i < ls; i++) {
		while(idx < rs && vec[l][i] > vec[r][idx]) idx++;
		cnt += idx;
	}
	f[dep][0] += cnt;
	f[dep][1] += 1LL * ls * rs - cnt;
	if(tr[p][0]) dfs(dep - 1, tr[p][0]);
	if(tr[p][1]) dfs(dep - 1, tr[p][1]);
}

void solve() {
	int n;
	scanf("%d", &n);
	for(int i = 1; i <= n; i++) {
		scanf("%d", &a[i]);
		insert(a[i], i);
	}
	dfs(30, 0);
	int num = 0;
	LL res = 0;
	for(int i = 30; i >= 0; i--) {
		if(f[i][0] <= f[i][1]) {
			res += f[i][0];
		}
		else {
			res += f[i][1];
			num += (1 << i);
		}
	}
	printf("%lld %d\n", res, num);
}

int main() {
    // freopen("in.txt", "r", stdin);
    solve();
    return 0;
}

CF 1416 C.XOR Inverse【字典树求逆序对】

原文：https://www.cnblogs.com/ZX-GO/p/14715753.html