题解：CF2121G Gangsta

· · 题解

太难了，数学真的很重要。

在长度为 n 的二进制字符串 str 的所有子串中，计算最大字符出现次数即 f(p) 的总和，可通过数学推导分解为两部分：

步骤 1: 函数分解

利用恒等式：

\max (x,y) = \frac{x + y + \vert x - y \vert}{2}

其中：

设 $x + y = len$（$len$ 表示子串长度）。 因此： $$ f(p) = \frac{len + \vert x - y \vert}{2} $$ 对所有子串求和，总答案为： $$ \frac{1}{2}(\sum len + \sum \vert x - y \vert ) $$ ## 步骤 2: 计算 $\sum len

对所有子串长度求和（固定公式）：

\sum len = \sum_{i=1}^{n} i(n - i + 1) = \frac{n(n+1)(n+2)}{6}

推导过程‌：

\sum i(n-i+1) = (n+1)\sum i - \sum i^2 = (n+1) \times \frac{n(n+1)}{2} - \frac{n(n+1)(2n+1)}{6} = n(n+1)(\frac{n+1}{2} - \frac{2n+1}{6}) = \frac{n(n+1)(n+2)}{6}

步骤 3: 计算 \sum \vert x - y \vert

关键转换，定义前缀和数组 pr：

pr_0 = 0\\ pr_i = pr_{i-1} + x\\ x=\begin{cases} 1 & str_i=1\\ -1 & str_i=0 \end{cases}

即累计 1 的贡献为 +1，0 的贡献为 -1。

子串 [l, r] 的 \vert x - y \vert = \vert pr_r - pr_{l-1} \vert（因 pr 差值即为 1 的个数与 0 的个数的差）。

问题转化为：计算所有下标对 0 \le i < j \le n 的 \vert pr_j - pr_i \vert 之和。

优化计算：

排序 pr 数组‌，设排序后为 g 数组。 贡献公式‌：排序后每个元素 g_i 的贡献为：

g_i \times (2i - n)

推导原理‌： 排序后，g_i 比前 i 个元素大，贡献 + g_i \times i。

总贡献：$g_i \times (i - (n - i)) = g_i \times (2i - n)$。 求和‌： $T = \sum_{i=0}^{n} g_i \times (2i - n)

举个粒子：

假设数组 g 有三个整数 a,b,c(a \le b\le c)。

T = (b - a) + (c - a) + (c - b) = 2c - 2a

用公式计算：a \times (0-2) + b \times (2-2) + c \times (4-2) = -2a + 0 + 2c = 2c - 2a

步骤 4: 最终答案

总答案为：

\frac{\frac{n(n+1)(n+2)}{6} + T}{2}

时间复杂度：

排序 pr 数组，O(n \log n)。

满足总 n \le 2×10^5 的限制。

代码：

#include <bits/stdc++.h>
using namespace std;
#define int long long
const int MAXN = 200016;
// const int MOD=
bool iscases = 1;
int pre[MAXN];

void gogogo() {
    int n;
    cin >> n;
    string s;
    cin >> s;
    s = "+" + s;
    pre[0] = 0;
    for (int i = 1; i <= n; i++) {
        pre[i] = pre[i - 1] + (s[i] == '1' ? 1 : (-1));
    }
    sort(pre, pre + 1 + n);
    int ans = 0;
    for (int i = 0; i <= n; i++) {
        ans += pre[i] * (2 * i - n);
    }
    cout << (n * (n + 1) * (n + 2) / 6 + ans) / 2 << '\n';
}

signed main() {
    ios::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    int T = 1;
    if (iscases) cin >> T;
    while (T--) {
        gogogo();
    }
    return 0;
}