ARC127D Sum of Min of Xor

tony102

2021 年 10 月 22 日

2165 次浏览

暂无评论

719字数

题解

[Link](https://atcoder.jp/contests/arc127/tasks/arc127_d)

你大可不必相信 CF 都是好题，但是 AtCoder 一定不会让你失望。

## Sol

先来考虑一个简单的问题：求 $\sum_{i<j} A_i \oplus A_j$ 。

考虑拆位，首先有贡献的肯定是不同位 $0$ 和 $1$ 配，那么统计每一位上的 $0,1$  数量，乘起来然后乘以 $(1 << i)$ （当前在 $i$ 位）。

现在要求的是 $\sum_{1 \leq i < j \leq n} \min{(A_i \oplus A_j, B_i \oplus B_j)}$ 。

首先两个数在二进制下取 $\min$，就是 $X=(000001\dots)_2 > Y = (0000001\dots)$ 这样的形式：前面一段前缀都相同，然后有一位的 $0/1$ 不同开始就有大小差别。现在关键的就是要比较第一个不同的这一位。

非常 NB 的比较方法：设 $D_i = A_i \oplus A_j \oplus B_i \oplus B_j$，那么 $C_i$ 哪一位上是 $1$，哪一位就是不同的。对 $D_i$ 再移一下项，可以得到更加有利于接下来步骤的形式：$D_i = A_i \oplus B_i \oplus A_j \oplus B_j$ ，这一样每个下标都是一样的位置，令 $C_i = A_i \oplus B_i$。

我们通过分治来计算每次分治区间内的数从哪里开始 $C_i$ 有 $0/1$（说明该区间内的数有大小差异）。具体地，当前分治的区间是 $[L,R]$，我们从左找到第一个 $C_i$ 为 $1$ 的位置 $i$，从右找到第一个 $C_i$ 为 $0$ 的位置 $j$，也就是 $[L,i)$ 为 $0$，$[i,j)$ 为 $1$。把区间中的每一个数在这一位的贡献独立计算。分类讨论即可，例如：$A_i, B_i, A_j$ 在当前枚举的位置上是 $0$,  $B_j$ 是 $1$，那么贡献就应该是 $A_i \oplus A_j$

## Idea

二进制挂钩请直接考虑拆位计算贡献，大小关系判断可以在位上异或判断，成对的贡献可以分治。

## Code

```cpp
#include <bits/stdc++.h>
using namespace std;

typedef long long LL;
const int SIZE = 2.5e5 + 5;

int n; LL ans;
int a[SIZE], b[SIZE], c[SIZE], w[2][2][2][2];

namespace GTR {
	const int bufl = 1 << 15;
	char buf[bufl], *s = buf, *t = buf;
	inline int fetch() {
		if (s == t) { t = (s = buf) + fread(buf, 1, bufl, stdin); if (s == t) return EOF; }
		return *s++;
	}
	inline int read() {
		int a = 0, b = 1, c = fetch();
		while (c < 48 || c > 57) b ^= c == '-', c = fetch();
		while (c >= 48 && c <= 57) a = (a << 1) + (a << 3) + c - 48, c = fetch();
		return b ? a : -a;
	}
} using GTR::read;

void exchange(int i, int j) {
    std::swap(a[i], a[j]), std::swap(b[i], b[j]), std::swap(c[i], c[j]);
}

void merge(int l, int r, int bit) {
    if (l > r) return;
    if (bit == -1) {
        int v[2];
        for (int i = 0; i < 18; ++ i) {
            v[0] = v[1] = 0;
            for (int j = l; j <= r; ++ j) ++ v[(a[j] >> i) & 1];
            ans += 1ll * v[0] * v[1] * (1ll << i);
        }
        return;
    }
    int i = l, j = r;
    while (i < j) {
        while (i <= r && !(c[i] >> bit & 1)) ++ i;
        while (i < j && c[j] >> bit & 1) -- j;
        if (i < j) exchange(i, j);
    }
    for (int k = 0; k < 18; ++ k) {
        memset(w, 0, sizeof(w)); int x = (1 << k);
        for (int o = l; o <= r; ++ o) 
            ++ w[o >= i][0][a[o] >> bit & 1][a[o] >> k & 1],
            ++ w[o >= i][1][a[o] >> bit & 1][b[o] >> k & 1];
        for (int p = 0; p < 2; ++ p)
            for (int q = 0; q < 2; ++ q) 
                ans += 1ll * w[0][p ^ q][p][0] * w[1][p ^ q][q][1] * x,
                ans += 1ll * w[0][p ^ q][p][1] * w[1][p ^ q][q][0] * x;
    }
    merge(l, i - 1, bit - 1), merge(i, r, bit - 1);
}

int main() {
    n = read();
    for (int i = 1; i <= n; ++ i) a[i] = read();
    for (int i = 1; i <= n; ++ i) b[i] = read(), c[i] = a[i] ^ b[i];
    merge(1, n, 17); 
    return printf("%lld\n", ans), 0;
}
```

最后修改：2021 年 10 月 27 日