跳转至

进阶优化思想

📌 一、前缀和

🎯 核心概念

什么是前缀和？
数列前 $i$ 项的和：

\[ pre_i \;=\; a_1 + a_2 + \cdots + a_i \]

它能做什么？
- 快速获取区间和、区间内质数/奇数/偶数个数等
- 可拓展至：前缀积、前缀异或等

🔍 一维前缀和

1️⃣ 定义

  • 令
    $$ pre_i = \sum_{j=1}^i a_j \quad\Longrightarrow\quad pre_i = a_1 + a_2 + \cdots + a_i $$
  • 例如：
  • $pre_1 = a_1$
  • $pre_2 = a_1 + a_2$
  • $\cdots$

  • $pre_n = a_1 + a_2 + \cdots + a_n$

  • 递推关系
    $$ pre_i = pre_{i-1} + a_i $$

// C++ 示例：维护一维前缀和
for (int i = 1; i <= n; i++) 
{
    cin >> a[i];
    pre[i] = pre[i - 1] + a[i];
}

💡 注意数据范围是否需要 long long。

性质

  • 区间和查询
    求区间 $i \sim j$ 内的数字之和，可以使用
    $$ pre_j - pre_{i-1} $$
    证明：
\[ \begin{aligned} pre_j &= a_1 + a_2 + \cdots + a_{i-1} + a_i + \cdots + a_j,\\ pre_{i-1} &= a_1 + a_2 + \cdots + a_{i-1},\\ \Rightarrow\, pre_j - pre_{i-1} &= a_i + \cdots + a_j \end{aligned} \]

常见应用

  • 给定 $l, r$
    直接用
    $$ pre_r - pre_{l-1} $$
    查询区间和。

  • 已知起点 $l$ 和区间长度 $len$
    终点为 $r = l + len - 1$。然后用
    $$ pre_r - pre_{l-1} $$
    查询区间和。

  • 注意
    前缀和不仅仅局限于 和。它主要是预处理的算法，通过一段前缀减去另一段前缀，得到某一段区间的信息。例如：

  • 区间内质数个数
  • 区间内奇数/偶数个数/含有 $3$ 的数字个数等
  • 区间异或值等

📚 二维前缀和

预处理：二维前缀和

  • 定义二维前缀和数组
    令 $\displaystyle pre[i][j]$ 表示矩阵 $a$ 中子矩阵 $[1..\,i]\times [1..\,j]$ 的元素之和，即
    $$ pre[i][j] \;=\; \sum_{x=1}^{i} \sum_{y=1}^{j} a_{x,y}, \quad 1 \le i \le n,\;1 \le j \le m. $$

  • 递推公式
\[ pre[i][j]=pre[i-1][j]+pre[i][j-1]-pre[i-1][j-1] + a_{i,j} \]

即 蓝 + 黄 + 绿 + 橙 = (蓝 + 黄) + (蓝 + 绿) - 蓝 + 橙 最终求得了 $pre_{i, j}$

查询公式 & 时间复杂度

  • 查询公式
    对于一次查询 $(x_1,y_1)$ 到 $(x_2,y_2)$ 范围内的子矩阵和，按下式计算：
\[\begin{aligned} &\sum_{i=x_1}^{x_2} \sum_{j=y_1}^{y_2} a_{i,j}\\ =&pre[x_2][y_2]-pre[x_1-1][y_2]-pre[x_2][y_1-1]+pre[x_1-1][y_1-1]. \end{aligned}\]

因此公式 $$ pre_{x_2,\ y_2}-pre_{x_1-1,\ y_2}-pre_{x_2,\ y_1-1}+pre_{x_1-1,\ y_1-1} $$

可以概括为 绿 + 蓝 + 橙 + 黄 - (绿 + 蓝) - (绿 + 橙) + 绿 = 黄。

  • 时间复杂度
  • 预处理：构造 $pre[i][j]$ 需要 $O(n \times m)$。
  • 查询：每次常数次访问 $pre$，$O(1)$，共 $Q$ 次故 $O(Q)$。

✏️ 二、差分

🔍 一维差分

🎯 核心概念

什么是差分？
差分是一种与前缀和相对的技巧，可视为前缀和的逆运算。通过差分数组，我们可以高效地处理某些“区间修改”类问题。

  • 设原数组为 $a_1, a_2, \ldots, a_n$，则差分数组 $b_1, b_2, \ldots, b_n$ 定义为：
\[ \begin{cases} b_1 = a_1,\\ b_i = a_i - a_{i-1}, \quad i = 2,3,\ldots,n. \end{cases} \]
  • 示例：
  • $b_1 = a_1$
  • $b_2 = a_2 - a_1$
  • $b_3 = a_3 - a_2$
  • $\ldots$

🔹 性质一：前缀还原原数组

  • 结论：
    原数组 $a_i$ 等于差分数组 $b$ 的前缀和：
    $$ a_i = \sum_{j=1}^i b_j. $$
  • 证明：
\[ \begin{aligned} a_n &= b_1 + b_2 + \cdots + b_n \\ &= a_1 + (a_2 - a_1) + (a_3 - a_2) + \cdots + (a_n - a_{n-1}) \\ &= a_n. \end{aligned} \]

例如：

\[ \begin{aligned} a_1 &= b_1,\\ a_2 &= b_1 + b_2 = a_1 + (a_2 - a_1),\\ a_3 &= b_1 + b_2 + b_3 = a_1 + (a_2 - a_1) + (a_3 - a_2). \end{aligned} \]

🔹 性质二：区间加法优化（核心应用）

  • 目标：
    将原数组中区间 $[l, r]$ 内的所有元素增加常数 $c$。

  • 差分做法：
    只需在差分数组上执行两步，时间 $O(1)$：

\[ \begin{cases} b_l \;+=\; c,\\ b_{r+1} \;-\!=\; c. \end{cases} \]

这样，恢复原数组时，$$a_l,\dots,a_r$$ 全部增加 $c$，其它位置不变。

具体证明

  1. 修改 $b_l += c$ 后：

    • 对于 $i < l$，$b_1,\dots,b_{l-1}$ 都不变，故 $a_1,\dots,a_{l-1}$ 不变。
    • 对于 $i \ge l$，$b_l$ 变为 $b_l + c$，恢复时从 $a_l$ 开始到末尾都多加 $c$。

  2. 再执行 $b_{r+1} -= c$：

    • 对于 $i \le r$，已经每项多加 $c$，故 $a_l,\dots,a_r$ 正确加 $c$。
    • 对于 $i \ge r+1$，在原本已加 $c$ 的基础上再减 $c$，恢复到原值。

因此，只改 $b_l$ 和 $b_{r+1}$ 即可完成区间加操作。

🔹 差分数组模板

  • 预处理差分数组（若初始 $a$ 不全 $0$）：
    for (int i = 1; i <= n; i++) 
{
    cin >> a[i];
    b[i] = a[i] - a[i - 1]; // 差分定义
}

    若原数组全为 $0$，则可跳过预处理，直接操作 b 数组。

  • 区间修改操作（将 [x, y] 范围内元素加 z）： 

    while (m--) 
{
    int x, y, z;
    cin >> x >> y >> z;
    b[x]     += z;
    b[y + 1] -= z;
}

  • 还原原数组并求值

  • 方法一：通过前缀和还原 $a$，顺便求最小/最大等： 

    int ans = 1e9;
for (int i = 1; i <= n; i++) 
{
    b[i] += b[i - 1]; // 前缀和还原 a[i]
    ans = min(ans, b[i]);
}

  • 方法二：先恢复 a[i] = a[i - 1] + b[i]，在做其他运算： 
    int ans = 1e9;
for (int i = 1; i <= n; i++) 
{
    a[i] = a[i - 1] + b[i]; // 前缀和还原 a[i]
    ans = min(ans, a[i]);
}

另一种写法：不需要预处理差分数组

直接维护差分数组 b，最后求 b 的前缀和得到每个 a[i] 的增量，然后累加初始值 a[i] 即可。

#include <bits/stdc++.h>
using namespace std;
constexpr int N = 2e5 + 5;
int n, a[N], b[N], q;
int main()
{
    cin >> n >> q;
    for (int i = 1; i <= n; i++)
        cin >> a[i];
    while (q--)
    {
        int x, y, z;
        cin >> x >> y >> z;
        b[x] += z;
        b[y + 1] -= z;
    }
    for (int i = 1; i <= n; i++)
    {
        b[i] += b[i - 1];
        a[i] += b[i];
        cout << a[i] << " ";
    }
    return 0;
}

🔸 二维差分

二维差分其实是二维前缀和的反操作，其关系为

\[ b_{i,j} = a_{i,j} - a_{i-1,j} - a_{i,j-1} + a_{i-1,j-1}. \]

类似一维差分中对区间进行统一加法，执行指令

\[ b_{i,j} \mathrel{+}= k \]

后，将使以 $(i,j)$ 为左上角、$(n,m)$ 为右下角的所有位置都增加 $k$。

子矩阵的修改：

可按如下调整二维差分数组：

  • $b_{x_1,y_1} \mathrel{+}= c$
    • 在位置 $(x_1,y_1)$ 处 $+c$，根据前缀和的性质，那么它影响的是 黄 + 蓝 + 橙 + 绿，多影响了 蓝 + 橙 + 绿，因此需要消除额外的影响。
  • $b_{x_1,y_2+1} \mathrel{-}= c$
    • $b_{x_1,y_2+1}-c$，会造成图中 绿 + 蓝 这两部分都减 $c$
  • $b_{x_2+1,y_1} \mathrel{-}= c$
    • $b_{x_2+1,y_1}-c$，会造成图中 绿 + 橙 这两部分都减 $c$
  • $b_{x_2+1,y_2+1} \mathrel{+}= c$
    • $b_{x_2+1,y_2+1}+c$，会造成图中 绿 这部分加 $c$

✨ 等差数列差分

🎯 前置知识：等差数列

  • 定义：若一个数列从第二项起，每项与前一项的差都相同，则称为等差数列。该差值称为“公差” $d$。
  • 记法：首项 $a_1$、末项 $a_n$、公差 $d$。

基本公式：
- 等差数列前 $n$ 项和：
$$ S_n = \frac{(a_1 + a_n)\times n}{2}. $$ - 若已知 $a_l$ 与 $a_r$，则公差：
$$ d = \frac{a_r - a_l}{r - l}. $$

🔹 题意

  • 给定 $m$ 次操作，每次选择区间 $[l, r]$，使该区间内所有数字加上一个等差数列，首项为 $s$、末项为 $e$。
  • 由此可算出公差：
    $$ d = \frac{e - s}{r - l}. $$

🔹 二次差分引入

  1. 一次差分：
    $$ b_i = a_i - a_{i-1}. $$
  2. 二次差分：
    $$ c_i = b_i - b_{i-1}. $$
  3. 当对区间 $[l, r]$ 增加等差数列时，只有少数几个位置的 $b$ 和 $c$ 会发生变化，具体如下：

🔸 二次差分示意

假设在 $[l, r]$ 区间加等差数列，首项 $s$、末项 $e$、公差 $d$。则：

下标 $l - 1$ $l$ $l + 1$ $\cdots$ $r$ $r + 1$ $r + 2$
原数组 $a$ 增量 0 $\color{red}{ s}$ $\color{red}{s + d}$ $\cdots$ $\color{red}{e}$ 0 0
一次差分 $b$ 0 $\color{red}{s }$ $\color{red}{d}$ $\cdots$ $\color{red}{d}$ $\color{red}{-e}$ 0
二次差分 $c$ 0 $\color{red}{s}$ $\color{red}{d - s}$ 0 0 $\color{red}{-(e + d)}$ $\color{red}{e}$

只需维护 $c_l, c_{l+1}, c_{r+1}, c_{r+2}$ 四个位置，恢复时做两次前缀和即可得到原数组 $a$。

🔹 完整代码（1D 等差更新 + 二次差分）

// 读入 n, m 省略
// c[] 为二次差分数组，b[] 为一次差分数组，a[] 为原数组
while (m--) 
{
    int l, r, s, e;
    cin >> l >> r >> s >> e;
    long long d = (e - s) / (r - l); // 计算公差
    c[l]     += s;
    c[l + 1] += d - s;
    c[r + 1] += -(e + d);
    c[r + 2] += e;
}
// 恢复：先通过一次累加还原 b，再通过一次累加还原 a
for (int i = 1; i <= n; i++) 
{
    b[i] = b[i - 1] + c[i];    // 一次前缀和还原到 b
    a[i] = a[i - 1] + b[i];    // 二次前缀和还原到 a
}

⏱ 时间复杂度：$O(n+m)$。

📌 三、离散化

🎯 核心概念

什么是离散化？
将原来值域很大的数据，映射到一个连续小范围内，便于开数组、使用树状数组、线段树等。

  • 作用：将稀疏的下标压缩成密集的小整数区间。

🔹 离散化步骤

  1. 收集所有待离散化的坐标

  2. 将每个操作或查询中出现的坐标值（如区间端点、查询点）都加入一个数组 lsh 中。

  3. 排序并去重

    sort(lsh + 1, lsh + n + 1);
int m = unique(lsh + 1, lsh + n + 1) - lsh - 1;

sort(lsh.begin(), lsh.end());
lsh.erase(unique(lsh.begin(), lsh.end()), lsh.end());

  4. 二分查找映射
    对于任意原坐标 x，使用
    int rank = lower_bound(lsh + 1, lsh + m + 1, a[i]) - lsh;

int rank = lower_bound(lsh.begin(), lsh.end(), x) - lsh.begin() + 1;

⭐️ 四、和式入门与技巧

🎯 核心概念

什么是和式？

用 ∑ 表示“连续相加”的表达式，例如：

\[ \sum_{i=1}^n i = 1 + 2 + 3 + \dots + n \]

嵌套示例：

\[ \sum_{i=1}^n \sum_{j=1}^m a_{i,j} \]
  • 在算法竞赛中，和式常用来表示循环累加过程，简化版即化为公式计算。

🔹 基本性质

  1. 可拆分（区间拆分）
\[ \begin{aligned} &\sum_{i=1}^{n} a_i \\ =&\sum_{i=1}^{m} a_i+\sum_{i=m+1}^{n} a_i. \end{aligned} \]
  1. 可分配（加法）
\[ \begin{aligned} &\sum_{i=1}^{n} (a_i + b_i) =&\sum_{i=1}^{n} a_i +\sum_{i=1}^{n} b_i. \end{aligned} \]
  1. 常数可提取
\[ \sum_{i=1}^{n} k \,a_i =k \sum_{i=1}^{n} a_i. \]

🔹 例题与化简技巧

例题 1 ：每个数被加了几次？

  • 设 $a_1, a_2, \dots, a_n$ 是一个数组。化简
\[ \sum_{i=1}^n \sum_{j=i}^n a_i. \]
  • 观察：内层和与 $j$ 相关，但 $a_i$ 不依赖 $j$，可提取：
\[ \begin{aligned} &\sum_{i=1}^n a_i \sum_{j=i}^n 1 \\ = &\sum_{i=1}^n a_i \cdot (n - i + 1). \end{aligned} \]

复杂度从 $O(n^2)$ 降为 $O(n)$。

例题 2 ：嵌套求和

  • 化简
\[ \sum_{i=1}^n \sum_{j=i}^n (a_i \times j). \]
  • 提取 $a_i$：
\[ \begin{aligned} &\sum_{i=1}^n a_i \sum_{j=i}^n j\\ =&\sum_{i=1}^n a_i \times \frac{(i + n)(n - i + 1)}{2}. \end{aligned} \]

🔹 交换求和次序（重要技巧）

  • 交换前：
\[ \sum_{i=1}^{n} \sum_{j=i}^{n} f(i, j). \]
  • 交换顺序：
\[ = \sum_{j=1}^{n} \sum_{i=1}^{j} f(i, j). \]

★ 有时交换顺序后更易化简。

例题 3 ：换序简化

  • $\displaystyle \sum_{i=1}^n \sum_{j=1}^i j$
  • 交换前含义：
    $(1) + (1 + 2) + (1 + 2 + 3) + \cdots + (1 + 2 + \cdots + n)$.
  • 交换后：
\[ \sum_{j=1}^n \sum_{i=j}^n j = \sum_{j=1}^n j \cdot (n - j + 1). \]

例题 4 ：双重和式

\[\begin{aligned} &\sum\limits_{i=1}^n \sum\limits_{j=i}^n a_i\times a_j\\ =&\sum\limits_{j=1}^n \sum\limits_{i=1}^j a_i\times a_j\\ =&\sum\limits_{j=1}^n a_j \sum\limits_{i=1}^j a_i\\ =&\sum\limits_{j=1}^n a_j\times pre[j] \end{aligned}\]

例题：[CSP-S2019 江西] 和积和

题目目标：

\[ \text{计算 }\ ans = \sum_{l=1}^n \sum_{r=l}^n \left( \sum_{i=l}^r a_i \times \sum_{j=l}^r b_j \right) \]

数据范围：$n\leq 5\times 10^5$。

解题思路：

定义前缀和：

  • $sa_x = \sum\limits_{i=1}^x a_i,\quad sb_x = \sum\limits_{i=1}^x b_i$

原式变为：

\[ ans = \sum_{l=1}^n \sum_{r=l}^n \left( (sa_r - sa_{l-1}) \times (sb_r - sb_{l-1}) \right) \]

展开乘积部分，得到：

\[ sa_r\cdot sb_r - sa_r\cdot sb_{l-1} - sa_{l-1}\cdot sb_r + sa_{l-1}\cdot sb_{l-1} \]

即：

\[\begin{aligned} ans &= \sum_{l=1}^n \sum_{r=l}^n \left( sa_r\cdot sb_r - sa_r\cdot sb_{l-1} - sa_{l-1}\cdot sb_r + sa_{l-1}\cdot sb_{l-1} \right)\\ &=\sum_{l=1}^n \sum_{r=l}^n sa_r\cdot sb_r-\sum_{l=1}^n \sum_{r=l}^n sa_r\cdot sb_{l-1} - \sum_{l=1}^n \sum_{r=l}^n sa_{l-1}\cdot sb_r+\sum_{l=1}^n \sum_{r=l}^n sa_{l-1}\cdot sb_{l-1} \end{aligned}\]

接下来将对四个部分分别求和。

  • 第一部分：$\sum\limits_{l=1}^n \sum\limits_{r=l}^n sa_r\cdot sb_r$

定义：$SAB_x = \sum\limits_{i=1}^x sa_i \cdot sb_i$

整项和为：$\sum\limits_{l=1}^n (SAB_n - SAB_{l-1})$

可预处理后 $O(n)$ 计算。

  • 第二部分：$\sum\limits_{l=1}^n \sum\limits_{r=l}^n sa_r \cdot sb_{l-1}$

提出常数：$= \sum\limits_{l=1}^n sb_{l-1} \cdot \sum\limits_{r=l}^n sa_r$

定义前缀和：$SA_x = \sum\limits_{i=1}^x sa_i$

则：$= \sum\limits_{l=1}^n sb_{l-1} \cdot (SA_n - SA_{l-1})$

可预处理后 $O(n)$ 计算。

  • 第三部分：$\sum\limits_{l=1}^n \sum\limits_{r=l}^n sa_{l-1} \cdot sb_r$

提出常数：$= \sum\limits_{l=1}^n sa_{l-1} \cdot \sum\limits_{r=l}^n sb_r$

定义：$SB_x = \sum\limits_{i=1}^x sb_i$

同理：$= \sum\limits_{l=1}^n sa_{l-1} \cdot (SB_n - SB_{l-1})$

可 $O(n)$ 求解。

  • 第四部分：$\sum\limits_{l=1}^n \sum\limits_{r=l}^n sa_{l-1} \cdot sb_{l-1}$

将常数项提出：$=\sum\limits_{l=1}^n sa_{l-1} \cdot sb_{l-1} \cdot \sum\limits_{r=l}^n 1 =\sum\limits_{l=1}^n sa_{l-1} \cdot sb_{l-1} \cdot (n - l + 1)$

直接枚举计算，总复杂度仍为 $O(n)$。

  • 最终：
\[\begin{aligned} ans &= \sum_{l=1}^n SAB_n - SAB_{l-1} \\ &\quad - \sum_{l=1}^n sb_{l-1} \cdot (SA_n - SA_{l-1}) \\ &\quad - \sum_{l=1}^n sa_{l-1} \cdot (SB_n - SB_{l-1}) \\ &\quad + \sum_{l=1}^n sa_{l-1} \cdot sb_{l-1} \cdot (n - l + 1) \end{aligned}\]
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
constexpr int N = 5e5 + 5, P = 1e9 + 7;
int n, a[N], b[N];
ll sa[N], sb[N];
ll SAB[N], SA[N], SB[N];
int main()
{
    ios::sync_with_stdio(false), cin.tie(0);
    cin >> n;
    for (int i = 1; i <= n; i++)
        cin >> a[i];
    for (int i = 1; i <= n; i++)
        cin >> b[i];
    for (int i = 1; i <= n; i++)
        sa[i] = (sa[i - 1] + a[i]) % P;
    for (int i = 1; i <= n; i++)
        sb[i] = (sb[i - 1] + b[i]) % P;
    for (int i = 1; i <= n; i++)
        SAB[i] = (SAB[i - 1] + sa[i] * sb[i]) % P;
    for (int i = 1; i <= n; i++)
        SA[i] = (SA[i - 1] + sa[i]) % P;
    for (int i = 1; i <= n; i++)
        SB[i] = (SB[i - 1] + sb[i]) % P;
    ll ans = 0;
    for (int i = 1; i <= n; i++)
    {
        ll sum1 = SAB[n] - SAB[i - 1];
        ll sum2 = sb[i - 1] * (SA[n] - SA[i - 1]) % P;
        ll sum3 = sa[i - 1] * (SB[n] - SB[i - 1]) % P;
        ll sum4 = sa[i - 1] * sb[i - 1] % P * (n - i + 1) % P;
        ans += sum1 - sum2 - sum3 + sum4;
        ans = (ans % P + P) % P;
    }
    cout << ans;
    return 0;
}

其余例题

例题一：区间质数

对区间 $[1,\,10^6]$ 进行埃氏筛法，得到布尔数组

\[ \text{is_prime}[i] = \begin{cases} \text{true}, & i \text{ 是质数},\\ \text{false}, & i \text{ 是合数}. \end{cases} \]

前缀和初始化： $pre[0]=0$，对 $1\le i\le10^6$，递推：

\[ pre[i] = pre[i-1] + (\text{is_prime}[i]\,?\,1:\,0) \]

其中 $pre[i]$ 表示区间 $[1,i]$ 内质数个数。

则区间质数个数为：$\text{ans} = pre[r] - pre[l-1]$

例题二：abc 子序列问题

题意： 给定一个长度为 $n,n\leq 5\cdot 10^5$ 的字符串 $s$，你可以将其中任意一个字符修改为另一个小写字母，最多修改一次。问：通过最多一次操作，字符串中子序列 $\text{abc}$ 的数量最多能达到多少？

若不进行任何操作，答案为原字符串中子序列 $\text{abc}$ 的个数。

  • 每一个字符 $\text{b}$ 都可能作为子序列 $\text{abc}$ 的中间字符。我们统计每个 $\text{b}$ 左侧的 $\text{a}$ 的数量与右侧的 $\text{c}$ 的数量，并累加乘积。
\[ \text{ans} = \sum_{j=1}^n [s_j = \texttt{'b'}] \cdot \left( \sum_{i=1}^{j} [s_i = \texttt{'a'}] \right) \cdot \left( \sum_{i=j}^{n} [s_i = \texttt{'c'}] \right) \]

使用前缀和与后缀和预处理 $\text{a}$ 与 $\text{c}$ 的出现次数，使得整体时间复杂度为 $O(n)$。

修改一个字符后的最大化策略

由于只能修改一个字符 $s_i$，我们可以枚举每个位置 $i$ 进行尝试，最终答案为：

\[ \text{最大值} = \text{原始答案} - \text{损失} + \text{新增} \]
  • 损失：指将原本的 $s_i$ 删除后，造成的 $\text{abc}$ 子序列减少量。
  • 新增：指将 $s_i$ 修改为另一个字符后，带来的新增 $\text{abc}$ 子序列数量。

枚举四种情况进行分析：

  • $s_i = \text{a}$，修改为 b 或 c。
  • $s_i = \text{b}$，修改为 a 或 c。
  • $s_i = \text{c}$，修改为 a 或 b。
  • $s_i = \text{other}$，修改为 a 或 b 或 c。

说白了就是研究每个位置 s[i] 分别当 a, b, c 对子序列 abc 的贡献。

a 的贡献：

当 s[i] 为 a 时，贡献的子序列数量为：

\[ \sum_{j = i+1}^n [s_j = \texttt{'b'}] \cdot \left( \sum_{k = j}^n [s_k = \texttt{'c'}] \right) \]
  • 即后面每个字符 b 在乘以 b 后面的 c 的个数。

记后缀数组 $\text{sc[j]}$ 表示 $j$ 到 $n$ 中字符 $\text{c}$ 的个数，则损失量可重写为：

\[ \sum_{j = i+1}^n [s_j = \texttt{'b'}] \cdot \texttt{sufc[j]} \]

进一步定义一个辅助数组：

\[ \texttt{SC[i]} = \sum_{j = i}^n [s_j = \texttt{'b'}] \cdot \texttt{sc[j]} \]

则 $a$ 的贡献为 SC[i + 1]。

b 的贡献：

新增：sa[i - 1] * sc[i + 1]。

  • sa[i - 1] 为 $[1,i-1]$ 中字符 a 的前缀和。
  • sc[i + 1] 为 $[i+1,n]$ 中字符 c 的后缀和。

c 的贡献：

$\texttt{SA[i]} = \sum\limits_{j=1}^{i-1} [s_j = \texttt{'b'}] \cdot \texttt{sa[j]}$

  • 即前面每个字符 b 在乘以 b 前面的 a 的个数。

则 $c$ 的贡献为 SA[i - 1]。

具体实现可以定义一个 f(int i, char c) 的计算贡献的函数。

注意 long long。

#include <bits/stdc++.h>
#define int long long
using namespace std;
const int N = 5e5 + 5;
int n, sa[N], sc[N];
int SC[N], SA[N]; 
string s;
int f(int i, char c)
{
    if (c == 'a') return SC[i + 1];
    if (c == 'b') return sa[i - 1] * sc[i + 1];
    if (c == 'c') return SA[i - 1];
    return 0;
} 
signed main()
{
    cin >> n >> s;
    s = " " + s;
    for (int i = 1; i <= n; i++)
        sa[i] = sa[i - 1] + (s[i] == 'a');
    for (int i = n; i >= 1; i--)
        sc[i] = sc[i + 1] + (s[i] == 'c');
    for (int i = n; i >= 1; i--)
        if (s[i] == 'b')
            SC[i] = SC[i + 1] + sc[i];
        else
            SC[i] = SC[i + 1];
    for (int i = 1; i <= n; i++)
        if (s[i] == 'b')
            SA[i] = SA[i - 1] + sa[i];
        else
            SA[i] = SA[i - 1];
    int ans = 0;
    for (int i = 1; i <= n; i++)
        if (s[i] == 'b')
            ans += sa[i - 1] * sc[i + 1];
    int temp = ans;
    for (int i = 1; i <= n; i++)
    {
        ans = max(ans, temp - f(i, s[i]) + f(i, 'a'));
        ans = max(ans, temp - f(i, s[i]) + f(i, 'b'));
        ans = max(ans, temp - f(i, s[i]) + f(i, 'c'));
    }
    cout << ans;
    return 0;
}

例题三：JOI 2021 Final

题意： 给定一个长为 $N,N \le 2 \times 10^5$ 的序列 $A_i$，你可以进行若干次操作：

  • 选定一个区间 $[L,R]$，让这个区间里的数加 $1$。

求至少多少次操作使得序列 $A$ 变为一个先升后降的序列。

对区间 $[l,r]$ 加 $1$，可转化为在差分数组上执行：

\[ b_l \mathrel{+}= 1,\quad b_{r+1} \mathrel{-}= 1 \]

先升后降的序列存在一个至高点 $i$，因此做法是：

  • 采用预处理左右部分，再枚举至高点进行合并。

根据差分数组的性质可得若满足递增就是 b[i] > b[i - 1]，递减则为 b[i] < b[i - 1]。

若以 $i$ 当至高点，则：

  • $b_2\ldots b_i >0$，$b_1$ 无所谓。
  • $b_{i+1}\ldots b_n <0$

换句话来说

  • $b_2\ldots b_i$ 中的非正数通过若干次加 $1$ 操作使得每一项均正。

  • $b_{i+1}\ldots b_n$ 中的非负数通过若干次减 $1$ 操作使得每一项均负。

因此预处理：

  • $pre_i$：使得 $a_1,\dots,a_i$ 严格递增的最少操作次数；
  • $suf_i$：使得 $a_i,\dots,a_n$ 严格递减的最少操作次数。

则答案为

\[ ans = \min_{1\le i\le n} (ans,\max(pre_i, suf_{i+1}\bigr)) \]

为何不是 $pre[i]+suf[i+1]$？

因为差分操作是绑定的，选择一个位置 $+1$ 必须同时选择一个位置 $-1$。

因此操作次数是前后操作次数的较大值。

考虑严格递增

为保证区间 $1\sim i$ 严格递增，必须有差分数组中 $b_2,\dots,b_i > 0$。

  • 若某 $b_j \le 0$，则至少需要对其加到 $1$（例如 $b_3 = -5$ 则需增加 $6$ 次）。

可通过前缀和预处理，求出前 $i$ 个位置调整到满足要求的最少操作次数。

for (int i = 2; i <= n; i++) // 第一项无所谓从第二项开始
{
    b[i] = a[i] - a[i - 1];
    if (b[i] <= 0)
        pre[i] = pre[i - 1] + abs(b[i]) + 1;
    else
        pre[i] = pre[i - 1];
}

预处理严格递减

同理，为使区间 $i\sim n$ 严格递减，要求相应位置调为恰好 $-1$（即从非负值降为 $-1$）。

  • 利用后缀和预处理，可以求出后半部分的最少操作次数。
for (int i = n; i >= 2; i++) 
{
    if (b[i] >= 0)
        suf[i] = suf[i + 1] + b[i] + 1;
    else
        suf[i] = suf[i + 1];
}

答案

for (int i = 1; i <= n; i++) // 枚举最高点
{
    ans = min(ans, max(pre[i], suf[i + 1]));
}

例题四：火烧赤壁

题意： 给定 $n$ 个区间 $[l,r)$，求区间并集的总长度。

数据范围：$n\leq 2\cdot 10^4$，$-2^{31}\leq l<r< 2^{31}$。

🔍 解题思路

由于区间的值域非常大（$[-2^{31}, 2^{31})$），我们无法直接建立数组来记录每个位置的覆盖情况，因此需要使用离散化 + 差分数组的方式来高效求解区间并的长度。

✅ 步骤一：离散化

首先将所有区间的左右端点提取出来，进行去重和排序，建立一个压缩坐标系。

「原始值域 → 离散化后的下标」

离散化的作用是将稀疏的端点映射为连续的数组下标，方便使用数组处理覆盖情况。

✅ 步骤二：差分数组

差分数组的核心思想是：

  • 对于区间 [l, r)：

    • 由于是左闭右开，因此实际是区间 $[l,r-1]$。

    • 在 l对应的离散下标位置 +1

    • 在 r对应的离散下标位置 -1

然后对差分数组做前缀和即可得到每一段区间的被覆盖次数。

✅ 步骤三：计算结果

对于差分数组求出的前缀和，如果某一段区间被覆盖次数大于 0，说明该段属于并集，统计其实际长度。

注意：离散化后相邻的离散点 lsh[i] 和 lsh[i+1]对应的原始值不一定是连续的，所以需计算实际长度：

lsh[i+1] - lsh[i]

✅ 时间复杂度分析

  • 离散化排序：$O(n \log n)$
  • 区间差分标记：$O(n)$
  • 遍历统计结果：$O(n)$

总复杂度：$O(n \log n)$

#include <bits/stdc++.h>

using namespace std;
const int N = 2e4 + 5;
int n, l[N], r[N], diff[N], lsh[N * 2], ans;
int main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);
    cin >> n;
    for (int i = 1; i <= n; i++)
    {
        cin >> l[i] >> r[i];
        lsh[i] = l[i], lsh[i + n] = r[i];
    }
    sort(lsh + 1, lsh + n * 2 + 1);
    int m = unique(lsh + 1, lsh + n * 2+ 1) - (lsh + 1);
    for (int i = 1; i <= n; i++)
    {
        l[i] = lower_bound(lsh + 1, lsh + m + 1, l[i]) - lsh;
        r[i] = lower_bound(lsh + 1, lsh + m + 1, r[i]) - lsh;
        diff[l[i]]++;
        diff[r[i]]--;
    }
    for (int i = 1; i < m; i++)
    {
        diff[i] += diff[i - 1];
        if (diff[i])
        {
            ans += lsh[i + 1] - lsh[i]; 
        }
    }
    cout << ans;
    return 0;
}

例题五：[NOIP2022] 种花

题意： 给定 $n \times m$ 的网格图，每个格子可能是土坑（1）或可种花（0）。定义两种图案：

  • C 形: 存在 $x_1,x_2,y_0,y_1,y_2$ 满足：
    • 第 $x_1$ 行 $[y_0,y_1]$ 全 $0$
    • 第 $x_2$ 行 $[y_0,y_2]$ 全 $0$
    • 第 $y_0$ 列 $[x_1,x_2]$ 全 $0$
    • $x_1+1<x_2$, $y_0<y_1,y_2$
  • F 形：在C形基础上增加：
    • 存在 $x_3 > x_2$ 使第 $y_0$ 列 $[x_1,x_3]$ 全 $0$
  • 数据范围：$1\leq n,m\leq 10^3$。

暴力思路：

先解决 C 形：

  • $x_1\in [1,n]$，$x_2\in [x_1+2,n]$，$y_0\in [1,m]$
  • 预处理 $r[i][j]$ 表示 $(i,j)$ 向右连续 $0$ 数量（含自身）
  • 判断 $y_0$ 列 $[x_1, x_2]$ 行是否全为 $0$
  • 答案增加：
\[ \texttt{C 形} = (r[x_1][y_0] - 1) \cdot (r[x_2][y_0] - 1) \]

判断是否全为 $0$

预处理 $d[i][j]$ 表示 $(i,j)$ 向下连续 $0$ 数量（含自身）

条件：$d[x_1][y_0] - d[x_2 + 1][y_0] = x_2 - x_1 + 1$

再解决 F 形：

基于 C 形的扩展：

  • 在 C 形的基础上，若第 $y_0$ 列从 $x_2$ 向下还能延伸 $0$，则构成 F 形
  • 答案贡献乘以：$d[x_2][y_0] - 1$
\[ \texttt{F 形} = (r[x_1][y_0] - 1) \cdot (r[x_2][y_0] - 1) \cdot (d[x_2][y_0] - 1) \]
void solve()
{
    cin >> n >> m >> C >> F;
    for (int i = 1; i <= n; i++) 
        for (int j = 1; j <= m; j++)
            cin >> a[i][j];
    vector<vector<int>> r(n + 1, vector<int>(m + 2, 0));
    for (int i = 1; i <= n; i++)
        for (int j = m; j >= 1; j--)
            r[i][j] = (a[i][j] == 0 ? r[i][j + 1] + 1 : 0);
    vector<vector<int>> d(n + 2, vector<int>(m + 1, 0));
    for (int i = n; i >= 1; i--)
        for (int j = 1; j <= m; j++)
            d[i][j] = (a[i][j] == 0 ? d[i + 1][j] + 1 : 0);
    ll resc = 0, resf = 0;
    for (int x1 = 1; x1 <= n; x1++)
    {
        for (int x2 = x1 + 2; x2 <= n; x2++)
        {
            for (int y0 = 1; y0 <= m; y0++)
            {
                if (a[x1][y0] == '1' || a[x2][y0] == '1') continue;
                if (d[x1][y0] - d[x2 + 1][y0] != x2 - x1 + 1) continue;
                resc = (resc + (r[x2][y0] - 1) * (r[x1][y0] - 1)) % mod;
                resf = (resf + (r[x2][y0] - 1) * (r[x1][y0] - 1) % mod * (d[x2][y0] - 1)) % mod;
            }
        }
    }
    cout << resc * C % mod << " " << resf * F % mod << "\n";
}

从 $O(n^2m)$ 到 $O(nm)$ 的优化

原式：

\[ ans = \sum_{x_1=1}^n \sum_{x_2=x_1+2}^n \sum_{y=1}^m (r[x_1][y]-1)(r[x_2][y]-1) \]

变形：

\[ ans = \sum_{x_2=3}^n \sum_{y=1}^m (r[x_2][y]-1) \cdot \underbrace{\left(\sum_{x_1=1}^{x_2-2} (r[x_1][y] - 1)\right)}_{sum[x_2][y]} \]

定义前缀和转移：

\[ sum[x][y] = \begin{cases} sum[x-1][y] + (r[x-2][y] - 1), & \text{若 $(x-2,y)\sim(x,y)$ 连续为 $0$} \\ 0, & \text{否则} \end{cases} \]

注意： 连续性仍需用 $d[x-2][y] \geq 3$ 判断。

void solve()
{
    vector<vector<int>> r(n + 1, vector<int>(m + 2, 0));
    for (int i = 1; i <= n; i++)
        for (int j = m; j >= 1; j--)
            r[i][j] = (a[i][j] == 0 ? r[i][j + 1] + 1 : 0);
    vector<vector<int>> d(n + 2, vector<int>(m + 1, 0));
    for (int i = n; i >= 1; i--)
        for (int j = 1; j <= m; j++)
            d[i][j] = (a[i][j] == 0 ? d[i + 1][j] + 1 : 0);
    Z resc = 0, resf = 0;
    vector<vector<Z>> sum(n + 1, vector<Z>(m + 1, 0));
    for (int x2 = 3; x2 <= n; x2++)
    {
        for (int y0 = 1; y0 <= m; y0++)
        {
            if (d[x2 - 2][y0] - d[x2 + 1][y0] == 3)
                sum[x2][y0] = sum[x2 - 1][y0] + (r[x2 - 2][y0] - 1);
            else   
                sum[x2][y0] = 0;
            if (a[x2][y0] == 0)
            {
                resc += (r[x2][y0] - 1) * sum[x2][y0];
                resf += (r[x2][y0] - 1) * (d[x2][y0] - 1) * sum[x2][y0];
            }
        }
    }
    cout << resc * c << " " << resf * f << "\n";
}