题目描述

给定一个长度为 $n$ 的数字字符串 $s = s_0s_1 \cdots s_{n-1}$（只包含字符 ‘0’ 到 ‘9’）。
一个子串 $s[l..r]$（即 $s_l s_{l+1} \cdots s_r$）被称为好串，需满足以下条件之一：
1. 子串长度为 1。
2. 子串长度大于 1，且可以被拆分成两个连续的非空子串 $p_1 = s[l..k]$ 和 $p_2 = s[k+1..r]$（其中 $l \le k < r$），使得 $p_1$ 和 $p_2$ 都是“连续非递减子串”。

一个字符串 $p = p_0p_1 \cdots p_{m-1}$ 是连续非递减子串 (CND)，如果对于所有的 $1 \le i < m$，都满足 $p_i = p_{i-1}$ 或者 $p_i = p_{i-1} + 1$。（这里的 $p_i$ 指的是字符对应的数字值）。

任务是计算给定字符串 $s$ 中所有好串子串的总数。

样例

输入:
12258
输出:
12

好串包括：1, 2, 2, 5, 8 (长度1, 5个)；12, 22, 25, 58 (长度2, 4个, 例如 25 可拆分为 2 和 5, 都是 CND)；122, 225 (长度3, 2个, 例如 122 可拆分为 1 和 22, 或 12 和 2)；1225 (长度4, 1个, 可拆分为 122 和 5)。总共 $5+4+2+1 = 12$ 个。

输入:
97856
输出:
13

好串包括：9, 7, 8, 5, 6 (长度1, 5个)；97, 78, 85, 56 (长度2, 4个, 例如 97 可拆分为 9 和 7)；978, 785, 856 (长度3, 3个, 例如 978 可拆分为 9 和 78)；7856 (长度4, 1个, 可拆分为 78 和 56)。总共 $5+4+3+1 = 13$ 个。

算法1 (扫描线 + 线段树)

$O(n \log n)$

思路分析

1. 好串的结构: 一个子串 $s[l..r]$ (长度 $>1$) 是好串，当且仅当存在一个分割点 $k$ ($l \le k < r$)，使得 $s[l..k]$ 和 $s[k+1..r]$ 都是连续非递减子串 (CND)。

2. 连续非递减子串 (CND): 一个串 $p$ 是 CND，如果相邻字符 $p_{i-1}, p_i$ 满足 $p_i = p_{i-1}$ 或 $p_i = p_{i-1} + 1$。

3. 预计算 CND 信息:

   • 我们可以预计算 ml[i]：以索引 i 结尾的最长 CND 子串的长度。
     $ml[i] = \begin{cases} 1 & \text{if } i=0 \text{ or } s_i \ne s_{i-1} \text{ and } s_i \ne s_{i-1}+1 \\ ml[i-1] + 1 & \text{if } i>0 \text{ and } (s_i = s_{i-1} \text{ or } s_i = s_{i-1}+1) \end{cases}$
   • 我们可以预计算 mr[i]：以索引 i 开头的最长 CND 子串的长度。
     $mr[i] = \begin{cases} 1 & \text{if } i=n-1 \text{ or } s_{i+1} \ne s_i \text{ and } s_{i+1} \ne s_i+1 \\ mr[i+1] + 1 & \text{if } i<n-1 \text{ and } (s_{i+1} = s_i \text{ or } s_{i+1} = s_i+1) \end{cases}$

4. 扫描线思路: 我们尝试用扫描线来统计好串的数量。考虑固定子串的起始位置 $l$，我们想知道有多少个结束位置 $r$ ($r \ge l$) 使得 $s[l..r]$ 是好串。

   • 如果 $r=l$，那么 $s[l..l]$ 是好串。
   • 如果 $r>l$，我们需要找到一个分割点 $k$ ($l \le k < r$) 使得 $s[l..k]$ 和 $s[k+1..r]$ 都是 CND。
   • 对于一个固定的分割点 $k$，它能作为 $s[l..k]$ (第一部分) 和 $s[k+1..r]$ (第二部分) 的分割点，需要满足：
     • $s[l..k]$ 是 CND：这要求 $l$ 必须在以 $k$ 结尾的最长 CND 子串的范围内，即 $l \ge k - ml[k] + 1$。令 $lk = k - ml[k] + 1$。
     • $s[k+1..r]$ 是 CND：这要求 $r$ 必须在以 $k+1$ 开头的最长 CND 子串的范围内，即 $r \le (k+1) + mr[k+1] - 1 = k + mr[k+1]$。令 $re = k + mr[k+1]$。
   • 所以，一个分割点 $k$ 可以使得子串 $s[l..r]$ 是好串，当且仅当 $lk \le l \le k$ 且 $k+1 \le r \le re$。

5. 事件定义与扫描:
   我们将问题转化为：对于每个可能的起始点 $l$（从 $0$ 到 $n-1$），计算有多少个结束点 $r$ ($r \ge l$) 使得 $s[l..r]$ 是好串，然后将这些数量加起来。
   我们使用扫描线，扫描变量是起始点 $l$。我们需要一个数据结构（线段树）来维护对于当前的 $l$，每个 $r$ ($r \ge l$) 是否能构成好串 $s[l..r]$。

   • 对于每个可能的分割点 $k$ ($0 \le k < n-1$)，它定义了一个“贡献区间”：当起始点 $l$ 落在 $[lk, k]$ 区间内时，它使得结束点 $r$ 落在 $[k+1, re]$ 区间内成为可能构成好串的候选。
   • 我们创建两类事件，按 $l$ 坐标排序：
     • 进入事件: 在 $l = lk$ 时触发。效果是：对于所有 $r \in [k+1, re]$，增加它们的“有效分割点计数” $1$。
     • 离开事件: 在 $l = k+1$ 时触发。效果是：对于所有 $r \in [k+1, re]$，减少它们的“有效分割点计数” $1$（因为当 $l > k$ 时， $k$ 不能再作为 $s[l..k]$ 的结束点了）。
   • 线段树: 维护区间 $[0, n-1]$ （对应可能的结束点 $r$）。线段树的每个叶子节点 $r$ 存储一个值 count[r]，表示对于当前的扫描线位置 $l$，有多少个有效的分割点 $k$ 可以使得 $s[l..r]$ 是好串的候选（即 $l \le k < r$ 且 $s[l..k]$ CND, $s[k+1..r]$ CND）。
   • 线段树需要支持区间加/减（对应事件）和查询。
   • 查询什么？对于当前的扫描线位置 $l$，我们需要计算有多少个 $r \ge l$ 满足 count[r] > 0 (或者加上 $r=l$ 的情况)。

6. 代码实现中的线段树:

   • 代码中的线段树维护的是 Info 结构，包含 min_val 和 cnt (取到最小值的叶子节点个数)。它支持区间加 Tag。
   • 当一个事件 (l, rs, re, +1) 发生时，它对线段树的区间 [rs, re+1) 执行 rangeApply 操作，将这个区间内所有叶子的 min_val 加 1。
   • 当一个事件 (l, rs, re, -1) 发生时，它对线段树的区间 [rs, re+1) 执行 rangeApply 操作，将这个区间内所有叶子的 min_val 减 1。
   • min_val 的初始值是 0。如果某个叶子 $r$ 的 min_val > 0，意味着对于当前的扫描线 $l$，至少存在一个有效的分割点 $k$，使得 $s[l..r]$ 是好串。
   • q_cov(n) 函数的作用是查询整个区间 [0, n) 中有多少个叶子节点 $r$ 的 min_val > 0。
     • 它先查询整个区间的聚合信息 root = st.rangeQuery(0, n)。
     • 如果 root.min_val > 0，说明所有叶子的 min_val 都大于 0，那么所有 $n$ 个可能的 $r$ 都满足条件，返回 $n$。
     • 如果 root.min_val == 0，说明存在 min_val 为 0 的叶子。root.cnt 记录了有多少个叶子的 min_val 恰好为 0。那么 min_val > 0 的叶子数量就是 $n - root.cnt$。返回 $n - root.cnt$。
   • 扫描线循环:
     • ans = n 初始化，包含了所有长度为 1 的好串。
     • 循环遍历按 l 排序的事件 ev。
     • l = e.l 是当前事件的触发位置。
     • if (l > last_l): 如果扫描线前进了 l - last_l 个位置，说明在 $[last_l, l-1]$ 这个范围内的所有起始点 $l’$，其对应的有效 $r$ 的集合与 $last_l$ 时相同。因此，将 $last_l$ 时计算出的好串数量（长度>1）q_cov(n) 乘以区间宽度 (l - last_l)，累加到 ans 中。
     • st.rangeApply(rs, re + 1, t): 根据当前事件 e 的类型（+1 或 -1）更新线段树。
     • last_l = l: 更新上次处理的扫描线位置。
     • 循环结束后，处理最后一段 $[last_l, n-1]$。

7. 复杂度:

   • 预计算 ml, mr: O(N)。
   • 生成事件: O(N)。
   • 排序事件: O(N log N)。
   • 线段树操作: 共 O(N) 次区间更新，每次 O(log N)。查询 q_cov 发生在事件点之间，最多 O(N) 次，每次 O(log N)。
   • 总时间复杂度: O(N log N)。

C++ 代码 (算法 1)

#include <bits/stdc++.h> // 引入所有标准库

using namespace std;
using i64 = long long; // 定义 i64 为 long long

// --- 线段树模板 ---
// Info: 线段树节点信息 (最小值 min_val, 最小值个数 cnt)
// Tag: 懒惰标记信息 (区间加的值 val)
template<class Info, class Tag>
struct LazySegmentTree {
    int n;
    std::vector<Info> info;
    std::vector<Tag> tag;
    // 构造函数和初始化
    LazySegmentTree() {}
    LazySegmentTree(int n) { init(n); }
    template<class T> LazySegmentTree(std::vector<T> w) { init(w); }
    void init(int n) {
        this->n = n;
        info.resize(4 << std::__lg(n)); // 大小设为 4*2^ceil(log2(n))
        tag.resize(4 << std::__lg(n));
    }
    template<class T> void init(std::vector<T> w) {
        init(w.size());
        std::function<void(int, int, int)> build = [&](int p, int l, int r) {
            if (r - l == 1) { info[p] = w[l]; return; } // 叶子节点
            int m = (l + r) / 2;
            build(2 * p, l, m); build(2 * p + 1, m, r);
            pull(p); // 合并子节点信息
        };
        build(1, 0, n);
    }
    // 合并左右子节点信息到父节点
    void pull(int p) { info[p] = info[2 * p] + info[2 * p + 1]; }
    // 将懒惰标记应用到当前节点信息
    void apply(int p, const Tag &v) { info[p].apply(v.val); tag[p].apply(v.val); }
    // 下推懒惰标记到子节点
    void push(int p) { apply(2 * p, tag[p]); apply(2 * p + 1, tag[p]); tag[p] = Tag(); /* 清空父节点标记 */ }
    // 单点修改 (本题未使用)
    void modify(int p, int l, int r, int x, const Info &v) { /* ... */ }
    void modify(int p, const Info &v) { /* ... */ }
    // 区间查询
    Info rangeQuery(int p, int l, int r, int x, int y) {
        if (l >= y || r <= x) { return Info(); } // 查询区间与当前节点区间无交集
        if (l >= x && r <= y) { return info[p]; } // 当前节点区间完全包含在查询区间内
        int m = (l + r) / 2;
        push(p); // 下推标记
        return rangeQuery(2 * p, l, m, x, y) + rangeQuery(2 * p + 1, m, r, x, y); // 递归查询左右子树并合并
    }
    Info rangeQuery(int l, int r) { return rangeQuery(1, 0, n, l, r); }
    // 区间应用懒惰标记 (区间加)
    void rangeApply(int p, int l, int r, int x, int y, const Tag &v) {
        if (l >= y || r <= x) { return; } // 应用区间与当前节点区间无交集
        if (l >= x && r <= y) { apply(p, v); return; } // 当前节点区间完全包含在应用区间内，打标记
        int m = (l + r) / 2;
        push(p); // 下推标记
        rangeApply(2 * p, l, m, x, y, v); // 递归应用到左右子树
        rangeApply(2 * p + 1, m, r, x, y, v);
        pull(p); // 更新父节点信息
    }
    void rangeApply(int l, int r, const Tag &v) { return rangeApply(1, 0, n, l, r, v); }
    // findFirst/findLast (本题未使用)
    template<class F> int findFirst(int p, int l, int r, int x, int y, F pred) { /* ... */ }
    template<class F> int findFirst(int l, int r, F pred) { /* ... */ }
    template<class F> int findLast(int p, int l, int r, int x, int y, F pred) { /* ... */ }
    template<class F> int findLast(int l, int r, F pred) { /* ... */ }
};

// 懒惰标记结构体
struct Tag {
    int val = 0; // 区间加的值
    void apply(const int &v) { val += v; } // 合并标记 (标记也是加法)
};
// 线段树节点信息结构体
struct Info {
    int min_val = 0; // 区间最小值
    int cnt = 0;     // 区间最小值出现的次数
    // 应用懒惰标记到节点信息
    void apply(const int &v) { min_val += v; }
};
// 合并两个子节点信息的函数
Info operator+(const Info &a, const Info &b) {
    Info res;
    if (a.min_val < b.min_val) { // 左子树更小
        res.min_val = a.min_val;
        res.cnt = a.cnt;
    } else if (a.min_val > b.min_val) { // 右子树更小
        res.min_val = b.min_val;
        res.cnt = b.cnt;
    } else { // 两边最小值相等
        res.min_val = a.min_val;
        res.cnt = a.cnt + b.cnt; // 次数相加
    }
    return res;
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    string s;
    cin >> s;
    int n = s.size();

    // 处理空串和单字符串的边界情况
    if (n == 0) { cout << 0 << '\n'; return 0; }
    if (n == 1) { cout << 1 << '\n'; return 0; }

    // 字符转整数 lambda
    auto c2i = [](char c) { return c - '0'; };

    // 预计算 ml[k]: 以 k 结尾的最长 CND 子串长度
    vector<int> ml(n);
    ml[0] = 1;
    auto calc_ml = [&](int k) {
        int cur = c2i(s[k]), prev = c2i(s[k - 1]);
        return (cur == prev || cur == prev + 1) ? ml[k - 1] + 1 : 1;
    };
    for (int k = 1; k < n; ++k) { ml[k] = calc_ml(k); }

    // 预计算 mr[i]: 以 i 开头的最长 CND 子串长度
    vector<int> mr(n);
    mr[n - 1] = 1;
    auto calc_mr = [&](int i) {
        int cur = c2i(s[i]), next = c2i(s[i + 1]);
        return (next == cur || next == cur + 1) ? mr[i + 1] + 1 : 1;
    };
    for (int i = n - 2; i >= 0; --i) { mr[i] = calc_mr(i); }

    // 事件结构体: l-触发扫描线位置, rs/re-影响的结束点范围, t-影响类型(+1/-1)
    struct E {
        int l, rs, re, t;
        bool operator<(const E& o) const { // 按 l 排序，相同 l 时 -1 事件优先
            return l == o.l ? t < o.t : l < o.l;
        }
    };
    vector<E> ev; // 事件列表

    // 添加事件的辅助函数
    auto add_ev = [&](int k) { // k 是分割点
        int lk = k - ml[k] + 1; // 第一部分 CND 的最早起始点
        // 第二部分 CND 的结束点 re = (k+1) + mr[k+1] - 1 = k + mr[k+1]
        // 注意代码中 k 的范围是 0 到 n-2, 所以访问 mr[k+1] 是安全的
        int re = k + mr[k + 1];
        if (re < k + 1) return; // 如果第二部分长度为0，无效分割
        int re_adj = min(re, n - 1); // 调整结束点范围不超过 n-1
        int lk_adj = max(0, lk); // 调整起始点范围不小于 0
        int rs_adj = k + 1; // 影响的结束点范围从 k+1 开始
        if (lk_adj <= k) { // 只有当起始点 l 在 [lk, k] 时，k 才是有效分割
            // 进入事件：当扫描线到达 lk 时，区间 [k+1, re] 的 count 加 1
            ev.push_back({lk_adj, rs_adj, re_adj, 1});
            // 离开事件：当扫描线到达 k+1 时，区间 [k+1, re] 的 count 减 1
            ev.push_back({k + 1, rs_adj, re_adj, -1});
        }
    };
    // 为每个可能的分割点 k 生成事件
    for (int k = 0; k < n - 1; ++k) { add_ev(k); }
    // 对事件按 l 排序
    sort(ev.begin(), ev.end());

    // 初始化线段树，所有叶子节点的 min_val=0, cnt=1 (表示初始 count[r]=0)
    vector<Info> init(n);
    for (int i = 0; i < n; ++i) { init[i].min_val = 0; init[i].cnt = 1; }
    LazySegmentTree<Info, Tag> st(init);

    // 查询线段树中值 > 0 的叶子节点数量
    auto q_cov = [&](int n) -> i64 {
        if (n <= 1) return 0; // 长度小于等于1的串没有长度>1的子串
        auto root = st.rangeQuery(0, n); // 查询整个区间 [0, n)
        // 如果全局最小值 > 0，说明所有 r 的 count[r] 都 > 0
        // 否则，说明存在 count[r] == 0，数量为 root.cnt
        return root.min_val > 0 ? n : n - root.cnt;
    };

    i64 ans = n; // 初始化答案为 n (所有长度为 1 的子串)
    int last_l = 0; // 上一次处理的扫描线位置

    // 执行扫描线
    for (const auto& e : ev) {
        int l = max(0, e.l); // 当前事件触发的 l
        // 如果扫描线前进了，计算 [last_l, l-1] 区间的贡献
        if (l > last_l) {
            // 对于 last_l <= l' < l, 有效 r 的数量等于 q_cov(n)
            ans += q_cov(n) * (l - last_l);
        }
        // 处理当前事件：更新线段树
        int rs = max(0, e.rs); // 事件影响的 r 起始点
        int re = min(n - 1, e.re); // 事件影响的 r 结束点
        if (rs <= re) { // 确保范围有效
            Tag t; t.val = e.t; // 创建懒惰标记
            st.rangeApply(rs, re + 1, t); // 应用区间更新 [rs, re+1)
        }
        last_l = l; // 更新 last_l
    }

    // 处理扫描线结束后，剩余的区间 [last_l, n-1] 的贡献
    if (n > last_l) {
        ans += q_cov(n) * (n - last_l);
    }

    cout << ans << '\n'; // 输出最终答案

    return 0;
}

算法2 (线性 DP)

$O(n)$

思路分析

1. 重新审视好串: 我们需要计算所有好串的数量。一个子串 $s[l..r]$ 是好串，要么 $l=r$，要么可以拆分为两个连续的 CND 子串。

2. 关键洞察: 算法 2 的代码非常简洁，它似乎在计算一个 pre 数组，然后基于这个数组直接计算答案。让我们尝试理解这个 pre 数组和计算逻辑。

3. 第一步：计算 pre1:
   代码中的第一个循环：
   cpp vector<int> pre(n); // 初始 pre 数组 for (int r = 1, l = 0; r < n; r++) { if (s[r] != s[r - 1] and s[r] != s[r - 1] + 1) { l = r; // 如果 s[r] 不能接在 s[r-1] 后面形成 CND，则新的 CND 段从 r 开始 } pre[r] = l; // pre[r] 存储以 r 结尾的 CND 子串的起始索引 } // pre[0] 默认为 0 (虽然代码没显式写，但 l 的初始值是 0)
   这个循环计算的 pre[r] (我们称之为 pre1[r]) 是以 $r$ 结尾的最长 CND 子串的起始索引。

4. 第二步：神秘的更新:
   代码中的第二个循环：
   cpp for (int i = n - 1; i > 0; i--) { pre[i] = pre[std::max(0, pre[i] - 1)]; }
   令第一次计算得到的数组为 pre1，第二次更新后得到的数组为 pre2。
   更新规则是 pre2[i] = pre1[pre1[i] - 1] (注意处理边界 pre1[i] - 1 < 0 时取 0)。
   pre1[i] 是以 $i$ 结尾的最长 CND 子串 $P_1 = s[\text{pre1}[i] .. i]$ 的起始索引。
   那么 pre1[i] - 1 是 $P_1$ 之前的那个字符的索引。
   pre1[pre1[i] - 1] 是以 $P_1$ 之前那个字符结尾的最长 CND 子串 $P_2$ 的起始索引。
   所以，pre2[i] 就是 $P_2$ 的起始索引。
   换句话说，pre2[i] 是这样一个起始索引 $l’$，使得 $s[l’ .. i]$ 恰好可以被拆分成两个连续的 CND 子串 $P_2 = s[l’ .. \text{pre1}[i]-1]$ 和 $P_1 = s[\text{pre1}[i] .. i]$。

5. 第三步：计算答案:
   代码中的最后一步：
   cpp i64 ans = 0; for (int i = 0; i < n; i++) { ans += i - pre[i] + 1; // pre[i] 是更新后的 pre2[i] }
   这行代码似乎在说：对于每个结束位置 $i$，所有起始位置 $l$ 满足 $l \ge \text{pre2}[i]$ 的子串 $s[l..i]$ 都是好串。并且，这样的 $l$ 的数量恰好是 $i - \text{pre2}[i] + 1$。
   为什么这个结论成立？

   • 证明 s[l..i] 是好串 if l >= pre2[i]:

     • Case 1: $l \ge \text{pre1}[i]$。这意味着 $s[l..i]$ 是以 $i$ 结尾的最长 CND 子串 $P_1$ 的一个后缀。任何 CND 串的非空后缀也是 CND。
       • 如果 $l=i$，长度为 1，是好串。
       • 如果 $l < i$，长度大于 1。我们可以将 $s[l..i]$ 拆分为 $s[l..l]$ (长度为1, CND) 和 $s[l+1..i]$ (作为 $P_1$ 的后缀，也是 CND)。根据好串定义 2，它是好串。（或者拆分为 $s[l..i-1]$ 和 $s[i..i]$）。
     • Case 2: $\text{pre2}[i] \le l < \text{pre1}[i]$。这意味着 $l$ 落在了 $P_2$ 的范围内。我们可以将 $s[l..i]$ 拆分为 $s[l .. \text{pre1}[i]-1]$ 和 $s[\text{pre1}[i] .. i]$。
       • 第一部分 $s[l .. \text{pre1}[i]-1]$ 是 $P_2$ 的后缀，所以是 CND。
       • 第二部分 $s[\text{pre1}[i] .. i]$ 就是 $P_1$，所以是 CND。
       • 根据好串定义 2， $s[l..i]$ 是好串。
     • 结合 Case 1 和 Case 2，我们证明了如果 $l \ge \text{pre2}[i]$，则 $s[l..i]$ 是好串。

   • 证明 s[l..i] 是好串 only if l >= pre2[i]:

     • 假设 $l < \text{pre2}[i]$。这意味着 $l$ 在 $P_2$ 开始之前。
     • 如果 $s[l..i]$ 是好串，那么必须存在一个分割点 $k$ ($l \le k < i$) 使得 $s[l..k]$ 和 $s[k+1..i]$ 都是 CND。
     • 因为 $l < \text{pre2}[i]$，并且 $\text{pre2}[i]$ 是 $P_2$ 的起始点，所以 $s[l..k]$ 不可能完全包含在 $P_2$ 或 $P_1$ 中（如果 $k < \text{pre1}[i]-1$）或者跨越 $P_2$ 和 $P_1$（如果 $k \ge \text{pre1}[i]-1$）。
     • 考虑 $s[k+1..i]$。它必须是 CND。这意味着 $k+1 \ge \text{pre1}[i]$，即 $k \ge \text{pre1}[i]-1$。
     • 现在考虑 $s[l..k]$。它必须是 CND。
       • 如果 $k = \text{pre1}[i]-1$，我们需要 $s[l .. \text{pre1}[i]-1]$ 是 CND。这要求 $l \ge \text{pre1}[\text{pre1}[i]-1] = \text{pre2}[i]$。这与我们的假设 $l < \text{pre2}[i]$ 矛盾。
       • 如果 $k > \text{pre1}[i]-1$，即 $k$ 在 $P_1$ 内部。我们需要 $s[l..k]$ 是 CND。但是， $s[\text{pre1}[i]-1]$ 和 $s[\text{pre1}[i]]$ 之间不满足 CND 条件（否则 $P_2$ 和 $P_1$ 会合并成一个更长的 CND 段）。既然 $l$ 在 $P_2$ 之前，而 $k$ 在 $P_1$ 内部，那么 $s[l..k]$ 必然跨越了 $P_2$ 和 $P_1$ 之间的断裂点，因此 $s[l..k]$ 不可能是 CND。
     • 因此，当 $l < \text{pre2}[i]$ 时，$s[l..i]$ 不可能是好串。

   • 综上所述，子串 $s[l..i]$ 是好串当且仅当 $l \ge \text{pre2}[i]$。

   • 对于固定的结束点 $i$，满足条件的起始点 $l$ 的范围是 $[\text{pre2}[i], i]$。这个范围包含的 $l$ 的数量是 $i - \text{pre2}[i] + 1$。
   • 算法 2 正确地计算了所有好串的总数。

6. 复杂度:

   • 第一步计算 pre1: O(N)。
   • 第二步计算 pre2: O(N)。
   • 第三步计算答案: O(N)。
   • 总时间复杂度: O(N)。

C++ 代码 (算法 2)

#include <bits/stdc++.h> // 引入所有标准库

using i64 = long long; // 定义 i64 为 long long

int main() {
    // 关闭 C++ 标准 IO 流与 C stdio 的同步，提高 cin/cout 速度
    std::ios::sync_with_stdio(false);
    // 解除 cin 和 cout 的绑定，进一步提速
    std::cin.tie(nullptr);

    std::string s; // 输入字符串
    std::cin >> s;

    int n = s.size(); // 字符串长度

    // pre[r] 将存储以 r 结尾的好串的最早可能起始位置 l (即 pre2[r])
    std::vector<int> pre(n); 
    // 第一步：计算 pre1[r] - 以 r 结尾的最长 CND 子串的起始索引
    for (int r = 1, l = 0; r < n; r++) {
        // 检查 s[r] 是否能接在 s[r-1] 后面形成 CND
        if (s[r] != s[r - 1] and s[r] != s[r - 1] + 1) {
            // 如果不能，新的 CND 段从 r 开始
            l = r;
        }
        // pre[r] 暂时存储 pre1[r]
        pre[r] = l; 
    }
    // pre[0] 隐含为 0

    // 第二步：利用 pre1 计算 pre2
    // pre[i] = pre[std::max(0, pre[i] - 1)] (其中 pre[i] 是 pre1[i])
    // 含义是 pre2[i] = pre1[pre1[i] - 1] (处理边界)
    for (int i = n - 1; i > 0; i--) {
        // 使用上一步计算出的 pre1 值来更新 pre 数组，使其存储 pre2 值
        pre[i] = pre[std::max(0, pre[i] - 1)]; 
    }
    // 更新后，pre[i] 存储的是 pre2[i]

    i64 ans = 0; // 初始化答案
    // 第三步：计算总和
    // 对于每个结束位置 i，好串的起始位置 l 的范围是 [pre2[i], i]
    // 数量为 i - pre2[i] + 1
    for (int i = 0; i < n; i++) {
        ans += (i64)i - pre[i] + 1; // 累加好串数量
    }

    // 输出最终答案
    std::cout << ans << "\n";

    return 0; // 程序正常结束
}