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 \le i < j \le n $ 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 $ ( $ 1 \le n \le 3 \cdot 10^5 $ ) — the number of elements in $ a $ .
Second line contains $ n $ space-separated integers $ a_1 $ , $ a_2 $ , …, $ a_n $ ( $ 0 \le a_i \le 10^9 $ ), 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.
样例:
样例输入1:
样例输出1:
样例输入2:
1
2
| 9
10 7 9 10 7 5 5 3 5
|
样例输出2:
样例输入3:
样例输出3:
思路:
实现:
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
66
67
68
69
| #include "ybwhead/ios.h"
#define int long long
const int N = 3e5 + 5;
typedef long long ll;
typedef vector<int> vi;
#define pb push_back
int n;
ll dp[N][2];
void Solve(vi &cur, int p)
{
if (p < 0 || cur.size() == 0)
{
return;
}
int cnt1 = 0, cnt2 = 0;
int ans1 = 0, ans2 = 0;
vi left, right;
for (int x : cur)
{
if ((x >> p) & 1)
{
ans2 += cnt1;
cnt2++;
right.pb(x);
}
else
{
ans1 += cnt2;
cnt1++;
left.pb(x);
}
}
dp[p][0] += ans2;
dp[p][1] += ans1;
Solve(left, p - 1), Solve(right, p - 1);
}
signed main()
{
yin >> n;
vi a(n);
for (int &x : a)
{
yin >> x;
}
reverse(a.begin(), a.end());
Solve(a, 30);
ll res = 0, ans = 0;
for (int i = 0; i <= 30; i++)
{
if (dp[i][0] <= dp[i][1])
{
ans += dp[i][0];
}
else
{
ans += dp[i][1];
res += 1 << i;
}
}
yout << ans << " " << res << endl;
return 0;
}
|