题目链接

CF1416C XOR Inverse

题目描述

You are given an array \(a\) consisting of \(n\) non-negative integers. You have to choose a non-negative integer \(x\) and form a new array \(b\) of size \(n\) according to the following rule: for all \(i\) from 1 to \(n\), \(b_{i}=a_{i} \oplus x(\oplus\) denotes the operation bitwise XOR).

An inversion in the \(b\) array is a pair of integers \(i\) and \(j\) such that \(1 \leq i and \(b_{i}>b_{j}\).
You should choose \(x\) in such a way that the number of inversions in \(b\) is minimized. If there are several options for \(x\) - output the smallest one.

输入格式

First line contains a single integer \(n\left(1 \leq n \leq 3 \cdot 10^{5}\right)-\) the number of elements in \(a\).
Second line contains \(n\) space-separated integers \(a_{1}, a_{2}, \ldots, a_{n}\left(0 \leq a_{i} \leq 10^{9}\right)\), where \(a_{i}\) is the \(i\) th element of \(a\).

输出格式

Output two integers: the minimum possible number of inversions in \(b\), and the minimum possible value of \(x\), which achieves those number of inversions.

题目翻译

给定长度为 \(n\left(1 \leq n \leq 3 \times 10^{5}\right)\) 的数列 \(\left\{a_{n}\right\}\left(0 \leq a_{n} \leq 10^{9}\right)\) ，请求出最小的整数 \(x\) 使 \(\left\{a_{n} \oplus x\right\}\) 的 逆序对数最少，其中 \(\oplus\) 是异或

输入格式

第一行 \(n\) ，第二行 \(\left\{a_{n}\right\}\)

输出格式

两个数，逆序对数和 \(x\)

解题思路

01trie

建立一棵下标01trie，即每插入一个数，在每个节点记录该数的下标，可知每个节点中的下标都是递增的，对于一棵子树来说，其右子树的值都要大于左子树，现在要求的即为右子树中下标小于左子树的对数，进而求出该子树的逆序对数量，当 \(x\) 对应该位的值为 \(1\) 时，即左右子树交换位置，逆序对的个数为总的对数减去原逆序对的数量，\(x\) 某一位为 \(1\) 当前仅当该位取 \(1\) 时的逆序对数量小于取 \(0\) 时的逆序对数量

• 时间复杂度：\(O(30n)\)

代码

// Problem: CF1416C XOR Inverse
// Contest: Luogu
// URL: https://www.luogu.com.cn/problem/CF1416C
// Memory Limit: 500 MB
// Time Limit: 2000 ms
// 
// Powered by CP Editor (https://cpeditor.org)

// %%%Skyqwq
#include 
 
//#define int long long
#define help {cin.tie(NULL); cout.tie(NULL);}
#define pb push_back
#define fi first
#define se second
#define mkp make_pair
using namespace std;
 
typedef long long LL;
typedef pair PII;
typedef pair PLL;
 
template  bool chkMax(T &x, T y) { return (y > x) ? x = y, 1 : 0; }
template  bool chkMin(T &x, T y) { return (y < x) ? x = y, 1 : 0; }
 
template  void inline read(T &x) {
    int f = 1; x = 0; char s = getchar();
    while (s < '0' || s > '9') { if (s == '-') f = -1; s = getchar(); }
    while (s <= '9' && s >= '0') x = x * 10 + (s ^ 48), s = getchar();
    x *= f;
}

const int N=9e6+5;
vector pos[N];
int trie[N][2],idx,n;
LL f[30][2]; 
void insert(int x,int id)
{
	int p=0;
	for(int i=29;~i;i--)
	{
		int t=x>>i&1;
		if(trie[p][t]==0)trie[p][t]=++idx;
		p=trie[p][t];
		pos[p].pb(id);
	}
}
void dfs(int u,int p)
{
	int l=trie[u][0],r=trie[u][1];
	if(l)dfs(l,p-1);
	if(r)dfs(r,p-1);
	if(!l&&!r)return ;
	LL res=0;
	int num=0;
	for(int i:pos[l])
	{
		while(num>n;
    for(int i=1;i<=n;i++)
    {
    	int x;
    	cin>>x;
    	insert(x,i);
    }
    dfs(0,29);
    LL inv=0;
    int x=0;
    for(int i=29;~i;i--)
    {
    	inv+=min(f[i][0],f[i][1]);
    	if(f[i][1]