题目理解

我们有两个长度为 $n$ 的二进制字符串 $a$ 和 $b$。定义一个 $n \times n$ 的网格，格子 $(i,j)$ 的值为 $a_i \oplus b_j$（异或）。

从 $(1,1)$ 出发，只能向下或向右移动。如果一条路径上所有格子值都为 $0$，则称为可行路径。

$f(x,y)$ 表示通过翻转 $a$ 或 $b$ 中的某些位（每次翻转一个位置），使得存在一条从 $(1,1)$ 到 $(x,y)$ 的可行路径的最少翻转次数。

求：

$$\sum_{x=1}^n \sum_{y=1}^n f(x,y)$$

---

第一步：可达条件化简

当前在格子 $(i,j)$ 时，$a_i \oplus b_j = 0$，即 $a_i = b_j$。

• 向下走到 $(i+1,j)$：需要 $a_{i+1} \oplus b_j = 0$，即 $a_{i+1} = b_j$。
  结合 $a_i = b_j$，得 $a_i = a_{i+1}$。
• 向右走到 $(i,j+1)$：需要 $a_i \oplus b_{j+1} = 0$，即 $a_i = b_{j+1}$。
  结合 $a_i = b_j$，得 $b_j = b_{j+1}$。

关键结论：
要能走到 $(x,y)$，必须满足：

$$a_1 = a_2 = \dots = a_x = b_1 = b_2 = \dots = b_y$$

即前缀 $a[1..x]$ 全相等，前缀 $b[1..y]$ 全相等，且这两个值相同。

---

第二步：$f(x,y)$ 的公式

设该公共值为 $v \in \{0,1\}$。

要达成这个状态：

• 对于 $a[1..x]$：如果 $v=0$，需要把其中所有 $1$ 翻成 $0$；如果 $v=1$，需要把其中所有 $0$ 翻成 $1$。
• 对于 $b[1..y]$：同理。

令：

• $\text{zeros}_a(x) = a[1..x]$ 中 $0$ 的个数
• $\text{ones}_a(x) = a[1..x]$ 中 $1$ 的个数
• 类似定义 $\text{zeros}_b(y), \text{ones}_b(y)$

则：

• 若选 $v=0$：代价 = $\text{ones}_a(x) + \text{ones}_b(y)$
• 若选 $v=1$：代价 = $\text{zeros}_a(x) + \text{zeros}_b(y)$

因此：

$$f(x,y) = \min\big(\text{ones}_a(x) + \text{ones}_b(y),\; \text{zeros}_a(x) + \text{zeros}_b(y)\big) $$

---

第三步：化简公式

注意：$\text{zeros}_a(x) + \text{ones}_a(x) = x$，$\text{zeros}_b(y) + \text{ones}_b(y) = y$。

设：

• $C_0(x,y) = \text{zeros}_a(x) + \text{zeros}_b(y)$
• $C_1(x,y) = \text{ones}_a(x) + \text{ones}_b(y)$

则：

$$f = \min(C_0, C_1) = \frac{C_0 + C_1}{2} - \frac{|C_0 - C_1|}{2} $$

而 $C_0 + C_1 = (x + y)$（因为每个位置都贡献一次 $0$ 或 $1$ 计数，总和就是总元素数）。

所以：

$$f(x,y) = \frac{x+y}{2} - \frac{|C_0 - C_1|}{2}$$

---

第四步：化简 $|C_0 - C_1|$

$$C_0 - C_1 = \big(\text{zeros}_a(x) - \text{ones}_a(x)\big) + \big(\text{zeros}_b(y) - \text{ones}_b(y)\big) $$

定义：

• $p_a(x) = \text{zeros}_a(x) - \text{ones}_a(x)$
• $p_b(y) = \text{zeros}_b(y) - \text{ones}_b(y)$

注意：$p_b(y)$ 可正可负。

那么：

$$|C_0 - C_1| = |p_a(x) + p_b(y)|$$

但是题解中用的是另一种定义（可能是为了对称性）：

设：

• $\text{pre}_a(x) = \text{zeros}_a(x) - \text{ones}_a(x)$
• $\text{pre}_b(y) = \text{ones}_b(y) - \text{zeros}_b(y)$

则：

$$C_0 - C_1 = \text{pre}_a(x) - \text{pre}_b(y)$$

因此：

$$|C_0 - C_1| = |\text{pre}_a(x) - \text{pre}_b(y)|$$

两种定义等价，只是符号变换。

---

第五步：求和

原和式：

$$\sum_{x=1}^n \sum_{y=1}^n f(x,y) = \sum_{x,y} \frac{x+y}{2} - \frac{1}{2} \sum_{x,y} |\text{pre}_a(x) - \text{pre}_b(y)| $$

第一部分：

$$\sum_{x=1}^n \sum_{y=1}^n \frac{x+y}{2} = \frac{1}{2} \left( \sum_{x=1}^n \sum_{y=1}^n x + \sum_{x=1}^n \sum_{y=1}^n y \right) $$$$= \frac{1}{2} \left( n \cdot \frac{n(n+1)}{2} + n \cdot \frac{n(n+1)}{2} \right) = \frac{n^2(n+1)}{2} $$

所以：

$$\text{ans} = \frac{n^2(n+1)}{2} - \frac{1}{2} \sum_{x=1}^n \sum_{y=1}^n |\text{pre}_a(x) - \text{pre}_b(y)| $$

---

第六步：计算 $\sum |\text{pre}_a(x) - \text{pre}_b(y)|$

我们有两个数组 $P_a[1..n]$ 和 $P_b[1..n]$（值域在 $[-n, n]$ 内）。

要求：

$$S = \sum_{i=1}^n \sum_{j=1}^n |P_a[i] - P_b[j]|$$

经典做法：

• 对 $P_a$ 和 $P_b$ 排序。
• 用双指针或前缀和计算。

具体地，先统计 $P_b$ 的频数分布（值域范围 $[-n, n]$，可偏移到非负索引）。
对每个 $P_a[i]$：

• 小于等于它的 $P_b$ 值的个数记为 $cnt$，它们的和记为 $sum$
• 贡献 = $P_a[i] \cdot cnt - sum$（这部分是 $P_a[i]$ 大于那些值的差）
• 加上另一部分：$(total\_sum\_b - sum) - P_a[i] \cdot (n - cnt)$（这部分是 $P_a[i]$ 小于那些值的差）

总 $S$ 可 $O(n \log n)$ 或 $O(n + \text{值域})$ 计算。

题解中用了一种更巧妙的离线方法：
先计算前缀频数，然后对每个 $i$ 用 $O(1)$ 查表，整体 $O(n)$。

---

第七步：最终算法

1. 读入 $n, a, b$。
2. 计算 $\text{pre}_a[i] = (\#0 - \#1)$ 在 $a[1..i]$。
3. 计算 $\text{pre}_b[i] = (\#1 - \#0)$ 在 $b[1..i]$。
4. 将 $\text{pre}_b$ 值映射到 $[0, 2n]$ 范围（加偏移 $n$）。
5. 用前缀和数组 $pf$ 统计 $\text{pre}_b$ 的频数和值的和。
6. 对每个 $\text{pre}_a[i]$，用二分或直接查 $pf$ 计算 $\sum |\text{pre}_a[i] - \text{pre}_b[j]|$。
7. 代入公式得到答案。

---

最终答案公式

$$\boxed{\text{ans} = \frac{n^2(n+1)}{2} - \frac{1}{2} \sum_{i=1}^n \sum_{j=1}^n |\text{pre}_a(i) - \text{pre}_b(j)|} $$

其中：

• $\text{pre}_a(i) = \#0_{a[1..i]} - \#1_{a[1..i]}$
• $\text{pre}_b(j) = \#1_{b[1..j]} - \#0_{b[1..j]}$

时间复杂度 $O(n \log n)$ 或 $O(n)$，空间 $O(n)$。