题意
给出一个长为\(n\)的数组\(\{a_i\}\), 用\(x\)异或数组中的每一个元素, 使得在新数组逆序对最少的情况下\(x\)最小.求满足题意的逆序对数和\(x\)
\(1 \le n \le 3 \cdot 10^5\)
题解
异或让我们考虑0-1Trie.
对于每一个数, 按照从高位到低位的顺序插入Trie, 并对其经过的每个节点维护该数字的下标. 具体来说,idx[u]记录了经过节点\(u\)的数字的下标. 由于我们按下标递增的顺序插入元素, 该数组是有序的.
有了idx[]，再结合一个显然的事实: 两个数的大小只取决于其最高位, 我们就可高效计算每一位所影响的逆序对(0-1Trie中,左子树代表的值小于右子树).
具体做法: 从高位开始自上而下遍历整棵0-1Trie. 设当前节点为\(u\), 当\(u\)的两个子节点均存在时, 修改该位才能对逆序对数目产生影响. 利用前面维护的下标, 我们可以在线性时间内计算该位对逆序对数目的贡献.
1
2
3
4
5
| int ptr = 0;
for(int x:idx[l]){
while(ptr < idx[r].size() and idx[r][ptr] < x)ptr++;
inv += ptr;
}
|
我们使用\(sum[][]\)来记录该结果.\(sum[i][0]\)表示不修改第\(i\)位所贡献的逆序对, \(sum[i][1]\)表示修改该位贡献的逆序对.容易看出修改该位后, 原本的逆序对变成了顺序对, 反之亦然.
1
2
| sum[dep][0] += inv;
sum[dep][1] += (ll)idx[l].size()*idx[r].size() - inv;
|
有了sum数组,答案便很容易统计:\(inv += \min(sum[i][0],sum[i][1])\). 而当\(sum[i][1] < sum[i][0]\)时, \(x\)的第\(i\)位为1.
代码
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
|
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
#define int long long
#define endl '\n'
const int maxn = 6e6+10;
ll sum[100][2];
struct Trie{
int size = 1;
int nxt[maxn][2];
vector<int>idx[maxn*2];
void clear(){
memset(nxt,0,sizeof(nxt));
}
void insert(int x,int pos){
int u = 0;
for(int i = 29;i >= 0;i--){
bool c = ((1ll<<i)&x);
if(!nxt[u][c])nxt[u][c] = size++;
u = nxt[u][c];
idx[u].push_back(pos);
}
}
void DFS(int pos,int dep){
int l = nxt[pos][0],r = nxt[pos][1];
if(l)DFS(l,dep-1);
if(r)DFS(r,dep-1);
if(!l or !r)return;
int ptr = 0,inv = 0;
for(int x:idx[l]){
while(ptr < idx[r].size() and idx[r][ptr] < x)ptr++;
inv += ptr;
}
sum[dep][0] += inv;
sum[dep][1] += (ll)idx[l].size()*idx[r].size() - inv;
}
}trie;
signed main(){
ios::sync_with_stdio(0);
cin.tie(nullptr);
int n;
cin >> n;
trie.clear();
for(int i = 1;i <= n;i++){
int x;
cin >> x;
trie.insert(x,i);
}
trie.DFS(0,29);
ll X = 0,inv = 0;
for(int i = 29;i >= 0;i--){
inv += min(sum[i][0],sum[i][1]);
if(sum[i][1] < sum[i][0])X += (1ll << i);
}
cout << inv << " " << X;
return 0;
}
|