字典树(codeforces1416C XOR Inverse)_Android

字典树(codeforces1416C XOR Inverse)

题目链接
题解:
我们建立01字典树，将每一个数依次插入，在途径的点记录该位的0/1。我们思考，对于一个数的每一位（字典树的每一层）都有可能形成逆序对。对于p节点。我们查看途径他的0，1序列。可以 $O (n)$ 记录其中<0,1>对和<1, 0>对的数量。我们把每一层的01和10对的数量记录下来。如果该位10对数量大于01对，即将这一位异或1反转。否则该位就是0。由此题启发，又找到一种 $O (n l o g n)$ 的统计逆序对的，使用01字典树方法。代码很短，和树状数组求逆序对差不多长。这种方法空间复杂度为 $O (n l o g n)$ 。似乎还可以带修？
下面是ac代码：

// % everyone
#include <cstdio>
#include<iostream>
#include<cstring>
#include <map>
#include <queue>
#include <set>
#include <cstdlib>
#include <cmath>
#include <algorithm>
#include <vector>
#include <string>
#include <list>
#include <bitset>
#include <array>
#include <cctype>
#include <time.h>


void read_f() { freopen("1.in", "r", stdin); freopen("1.out", "w", stdout); }
void fast_cin() { std::ios::sync_with_stdio(false); std::cin.tie(); }
void run_time() { std::cout << "ESC in : " << clock() * 1000.0 / CLOCKS_PER_SEC << "ms" << std::endl; }
template <typename T>
bool bacmp(const T & a, const T & b) { return a > b; }
template <typename T>
bool pecmp(const T & a, const T & b) { return a < b; }

#define ll long long
#define ull unsigned ll
#define _min(x, y) ((x)>(y)?(y):(x))
#define _max(x, y) ((x)>(y)?(x):(y))
#define max3(x, y, z) ( max( (x), max( (y), (z) ) ) )
#define min3(x, y, z) ( min( (x), min( (y), (z) ) ) )
#define pr(x, y) (make_pair((x), (y)))
#define pb(x) push_back(x)
using namespace std;
const int N = 3e5+5;
const int inf =0x3f3f3f3f;
vector<bool> vc[N*40];
int a[N*40];
int tr[N][2], tot = 1;
void insert(int p, int te, int dep, int i)
{
	if (dep < 0) return;
	vc[p].pb((bool)(te & (1 << dep) ) );
	int g = (bool) ( te & (1 << dep) );
	if (tr[p][g] == 0)
		tr[p][g] = ++tot;
	insert(tr[p][g], te, dep-1, i);
}
bool vis[N];
ll ans[N][2];
void sol(int p, int dep)
{
	if (p == 0) return;
	ll cnt0 = 0, cnt1 = 0;
	for (int i = 0; i < vc[p].size(); i++)
	{
		if (vc[p][i] == 0)
		{
			ans[dep][1] += cnt1;
			cnt0++;
		}
		else
		{
			ans[dep][0] += cnt0;
			cnt1++;
		}
	}
	sol(tr[p][0], dep+1);
	sol(tr[p][1], dep+1);
}
int main()
{
	int n;
	scanf("%d", &n);
	for (int i = 1; i <= n; i++)
	{
		int te; scanf("%d", &te);
		insert(1, te, 30, i);
	}
	sol(1, 1);
	ll sum = 0, res = 0;
	for (int i = 1; i <= 31; i++)
	{
		if (ans[i][1] > ans[i][0])
		{
			res = res << 1 | 1;
			sum += ans[i][0];
		}
		else
		{
			res = res << 1;
			sum += ans[i][1];
		}
	}
	printf("%lld %lld\n", sum, res);
	return 0;
}