E. XOR Inverse
题意
给出一个长度为n<3e5的数组a
求一个x使得 bi=ai^x得到 新的数组bi
它的逆序对inv个数最少
输出最小的x和对应数组b 的逆序对个数
题解
当许多数的前x位二进制相同时 决定它们之间是否形成逆序对的就是第x位
比如对于样例8 10 3
变为二进制为 01000 01010 00011
对于第1位二进制 则分为1000 1010 | 0011
假如x此位为0 那么异或得到的b中 会产生 2个逆序对
假如x此位为1 那么异或得到的b中 会产生 0个逆序对
所以x此为需要为1来减少b数组中的逆序对
根据 1000 1010 的第3位二进制分组 1000 | 1010 它们前两位都相同
假如x此位为0 那么异或得到的b中会产生0个逆序对
假如x此位为1 那么异或得到的b中会产生1个逆序对
所以得到x=8 b数组逆序对为0
上面描述的就是根据每一位上的bit分治递归求解的过程
对于分治分组求逆序对可以先将n个数转化成二进制串插入到字典树中
那么就能直接通过字典树某个结点上记录二进制的前缀相同的串的个数
字典树介绍
点中的编号记为point
树的空间上限取决于能延伸出多少点
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
60
61
62
63
64
65
| #include <bits/stdc++.h>
using namespace std;
typedef long long ll;
#define endl '\n'
#define Turnoff std::ios::sync_with_stdio(false)
#define P pair<ll,int>
const ll Max=3e5+5;
const ll Mod=998857459;
const int INF=0x3f3f3f3f;
vector<int>mp[Max<<4];
int id=1,maxpoint=0;
int tree[2][Max<<4];
ll sum[2][33];
void add(int num,int pos){
int point=0;
for(int i=31;i>=0;i--){
int bit=((num>>i)&1);
if(!tree[bit][point])tree[bit][point]=id++;
point=tree[bit][point];
mp[point].push_back(pos);
}
}
void solve(int point,int bit){
int L=tree[0][point],R=tree[1][point];
if(L)solve(L,bit-1);
if(R)solve(R,bit-1);
if(!L||!R)return;
ll inv=0,cnt=0;
for(auto pos:mp[L]){
while(cnt<mp[R].size()&&mp[R][cnt]<pos)cnt++;
inv+=cnt;
}
sum[0][bit]+=inv;
sum[1][bit]+=1ll*mp[R].size()*mp[L].size()-inv;
}
int main() {
Turnoff;
int n;cin>>n;
for(int i=1;i<=n;i++){
int temp;cin>>temp;
add(temp,i);
}
solve(0,31);
ll inv=0,x=0;
for(int i=31;i>=0;i--){
inv+=min(sum[0][i],sum[1][i]);
if(sum[1][i]<sum[0][i])x+=(1ll<<i);
}
cout<<inv<<" "<<x<<endl;
}
|