题意简述
Yuri 得到两个长度均为 $n$ 的二进制字符串 $a$ 和 $b$。这两个字符串动态地定义了一个 $n \times n$ 的网格。令 $(i,j)$ 表示第 $i$ 行、第 $j$ 列的单元格。单元格 $(i,j)$ 的初始值为 $a_i \oplus b_j$，其中 $\oplus$ 表示按位异或操作。
Yuri 的旅程总是从单元格 $(1,1)$ 开始。从单元格 $(i,j)$，她只能向下移动到 $(i+1,j)$，或向右移动到 $(i,j+1)$。如果存在一条合法路径，使得路径上所有单元格（包括 $(1,1)$）的值均为 $0$，则她的旅程是可行的。
在出发前，她可以进行如下操作任意次：
选择一个下标 $1 \leq i \leq n$，翻转 $a_i$ 或 $b_i$ 的值（$0$ 变为 $1$，$1$ 变为 $0$）。网格也会随之发生相应变化。
设 $f(x,y)$ 表示 Yuri 为了能够到达单元格 $(x,y)$ 所需的最小操作次数。你需要求出所有 $1 \leq x,y \leq n$ 的 $f(x,y)$ 的和。
注意，这 $n^2$ 个情况是相互独立的，也就是说在每种情况中都假设网格处于初始状态（即没有真正执行操作）。
思路分析
由于按位异或是相同为 $0$，不同为 $1$，那如果要这条路径可行，就需要这条路径所有的位置对应的 $a$ 和 $b$ 都相同。
又由于只能向右向下走，所以可以进一步推出，到达 $(x, y)$ 需要 $a_i = b_j(i \in [1, x], j=[1, y])$。
那么问题就转化为如何用最少的操作数使所有的 $a_i$ 和 $b_j$ 都相等。要么都转换为 $0$，要么都转换为 $1$.
记 $\text{cnt}0$ 表示沿途的 $0$ 的个数，$\text{cnt}_0=\sum\limits{i=1}^x (1-ai) + \sum\limits{j=1}^y(1-b_i)$。
同理，$\text{cnt}1=\sum\limits{i=1}^x ai + \sum\limits{j=1}^y b_i$。
那么 $f(x, y) = \min(\text{cnt}_0, \text{cnt}_1)$。
但是我们要求 $\sum f(x, y)$，其中的 $\min$ 很不方便。
于是根据 $\min(x, y) = \dfrac{x+y}{2} - \dfrac{|x-y|}{2}$，原式转化为了 $\sum f(x, y)=\sum(\dfrac{\text{cnt}_0+ \text{cnt}_1}{2} - \dfrac{|\text{cnt}_0 - \text{cnt}_1|}{2})$。
又由于 $\text{cnt}_0 + \text{cnt}_1 = x+y$，那么第一项就可以化为 $\dfrac{n^2(n+1)}{2}$。
接下来处理第二项。
拆开 $\text{cnt}_0 - \text{cnt}_1$，得到
记 $\text{preA}_x = \text{cnt}_0(x, 0) - \text{cnt}_1(x, 0)$，$\text{preB}_y = \text{cnt}_1(0, y) - \text{cnt}_0(0, y)$
原式就转化为 $\sum f(x, y) = \dfrac{n^2(n+1)}{2} - \sum |\text{preA}_x-\text{preB}_y|$.
但是计算 $|\text{preA}_x-\text{preB}_y|$ 仍然是需要 $n^2$ 次操作。核心在于不知道 $\text{preA}_x $ 和 $\text{preB}_y$ 之间的大小关系。
那如果假设我们固定一个 $x$，我们实际上就能以 $\log$ 的复杂度找到所有比 $\text{preA}_x$ 小的 $\text{preB}_y$。
所以，我们对所有 $\text{preB}_y$ 排序，然后预处理出前缀和，通过二分我们就能在 $O(n \log n)$ 的复杂度内解决问题。
总结
现在做 1900 感觉有点早。
收获就是 $\min(x, y) = \dfrac{x+y}{2} - \dfrac{|x-y|}{2}$ 的转化吧。