题解：CF2131F Unjust Binary Life

Claire0918 · 2025-09-14 21:45:34 · 题解

我们注意到 a_x \oplus b_y = 0 当且仅当 a_x = b_y，所以能从 (1, 1) 走到 (x, y) 当且仅当

分类讨论这个值是 0 还是 1。我们记 s_i = \sum_{k = 1}^{i} a_k, t_i = \sum_{k = 1}^{i} b_k，那么这个值为 0 时 f(x, y) = s_x + t_y，为 1 时 f(x, y) = (x - s_x) + (y - t_y)，于是 f(x, y) = \min\{s_x + t_y, x + y - s_x - t_y\}，答案即求

我们考虑是否有 s_x + t_y > x + y - s_x - t_y，即 2t_y - y > x - 2s_x。将 x 和 y 的贡献拆开，一个 y 在所有满足该条件的 x 上贡献 y - t_y，否则贡献 t_y。我们设一个 x 中有 k 个 y 满足条件，那么 x 就有 k 次贡献 x - s_x，n - k 次贡献 s_x。我们仅需对于任何 x 维护所有满足条件的 y 的 \sum_y 1, \sum_y y, \sum_y t_y 即可。我们注意到 2t_y - y 和 x - 2s_x 都是 \mathcal{O}(n) 的，于是我们直接差分即可维护，时间复杂度 \mathcal{O}(n)。

Code：

#include<bits/stdc++.h>
#define mem(a, v) memset(a, v, sizeof(a))

using namespace std;

const int maxn = 2e5 + 10;

int t, n;
long long res;
int a[maxn], b[maxn], prea[maxn], preb[maxn], pd[maxn << 1], *d = pd + maxn;
long long pspos[maxn << 1], psval[maxn << 1], *spos = pspos + maxn, *sval = psval + maxn;

int main(){
    scanf("%d", &t);
    while (t--){
        scanf("%d", &n), getchar(), res = 0;
        for (int i = -n; i <= n + 1; i++){
            d[i] = spos[i] = sval[i] = 0;
        }
        for (int i = 1; i <= n; i++){
            prea[i] = prea[i - 1] + (a[i] = getchar() - '0');
        }
        getchar();
        long long sum = 0;
        for (int i = 1; i <= n; i++){
            sum += (preb[i] = preb[i - 1] + (b[i] = getchar() - '0'));
            const int p = (preb[i] << 1) - i;
            d[p]++, spos[p] += i, sval[p] += preb[i];
        }
        for (int i = n; i >= -n; i--){
            d[i] += d[i + 1], spos[i] += spos[i + 1], sval[i] += sval[i + 1];
        }
        for (int i = 1; i <= n; i++){
            const long long p = i - (prea[i] << 1), k = d[p];
            res += k * (i - prea[i]) + (n - k) * prea[i] + spos[p] - sval[p] + (sum - sval[p]);
        }
        printf("%lld\n", res);
    }

return 0;
}