辞书 - 题解

标签与难度

标签: 思维题, 贪心, 构造, 数据结构, 模拟难度: 1200

题目大意喵~

主人你好呀，这道题是这样的喵~

我们有一个长度为 $n$ 的字符串 $s$ 。接下来会有 $q$ 次操作。每一次操作，会给我们两个数字 $l$ 和 $r$ 。我们需要做一件事：把所有以位置 $l$ 为起点，并且以子串 s[l..r] 为前缀的子串都给“标记”上。

每次操作结束后，都需要我们告诉它，到目前为止，总共有多少个不同的子串被标记了呢？

举个例子，如果字符串是 "abcde" ( $n=5$ )，一次操作是 l=2, r=3。

子串 s[2..3] 是 "bc"。
以位置 2 为起点，并且以 "bc" 为前缀的子串有哪些呢？
- s[2..3] ( "bc" )
- s[2..4] ( "bcd" )
- s[2..5] ( "bcde" )
所以这次操作会标记这 3 个子串。如果这是第一次操作，那么答案就是 3。

如果下一次操作是 l=2, r=4，它会标记以 "bcde" 为前缀的子串，也就是 s[2..4] 和 s[2..5]。但这两个我们之前已经标记过啦，所以新增加的被标记子串是 0 个，总数还是 3。

如果再下一次操作是 l=2, r=2，它会标记以 "b" 为前缀的子串，即 s[2..2], s[2..3], s[2..4], s[2..5]。其中 s[2..2] ("b") 是新的，所以总数会变成 4。

看明白了吗，喵？我们要的就是每次操作后，被标记过的不同子串的总数~

解题思路分析

喵哈哈，这道题看起来和字符串有关，但仔细一想，好像被出题人小小的“欺骗”了一下呢！让我来揭开它的神秘面纱吧~

首先，我们来分析一次查询 (l, r) 到底标记了哪些子串。题目说，要标记所有以 l 为起点，且以 s[l..r] 为前缀的子串。一个以 l 为起点的子串可以写成 s[l..k] 的形式，其中 $k \ge l$ 。要让 s[l..r] 成为 s[l..k] 的前缀，只需要 $k \ge r$ 就行啦。所以，一次查询 (l, r) 实际上标记了所有形如 s[l..k] 且 $k \in [r, n]$ 的子串。

这些子串是： $s[l..r], s[l..r+1], s[l..r+2], \dots, s[l..n]$ 总共有 $n - r + 1$ 个。

关键点来啦！题目要求的是所有被标记过的不同子串的总数。这意味着，对于同一个子串，就算被标记了十次、一百次，我们也只算它一次！

我们注意到，所有查询都只跟起点 l 和右端点 r 有关。对于一个固定的起点 l，所有相关的查询 (l, r_1), (l, r_2), \dots 都会影响同一批“以 l 为起点的子串”。不同起点的子串是完全独立的，不会互相影响。比如，s[1..2] 和 s[2..3] 永远不可能是同一个子串。

这启发我们，可以对每个起点 l (从 1 到 $n$ ) 分开考虑！

对于某个固定的起点 l，假设我们收到了两个查询：(l, r_a) 和 (l, r_b)。

查询 (l, r_a) 标记了所有 $s[l..k]$ 其中 $k \ge r_a$ 。
查询 (l, r_b) 标记了所有 $s[l..k]$ 其中 $k \ge r_b$ 。

如果我们想知道这两个查询总共标记了哪些以 l 为起点的子串，其实就是取这两个集合的并集。这个并集是所有 $s[l..k]$ 其中 $k \ge \min(r_a, r_b)$ 。喵！发现了嘛？对于一个固定的起点 l，真正起作用的，是所有查询中那个最小的 r！

比如说，对于起点 l=2，我们先后收到了查询 (2, 4) 和 (2, 3)。

(2, 4) 标记了 $k \ge 4$ 的子串。
(2, 3) 标记了 $k \ge 3$ 的子串。综合起来，所有 $k \ge 3$ 的子串都被标记了。效果等同于只进行了一次 (2, 3) 的查询。如果之后又来一个查询 (2, 5)，因为 $5 > 3$ ，它标记的子串集合是已经被 (2, 3) 覆盖的，所以不会增加任何新的被标记子串。

所以，我们可以为每个起点 l 维护一个值，就叫它 min_r[l] 吧，表示对于起点 l，我们目前遇到的所有查询中最小的那个 r。

一开始，对于任何 l，我们都还没有收到任何查询，可以说 min_r[l] 是一个非常大的值。多大呢？我们可以把它初始化为 $n+1$ 。为什么是 $n+1$ 呢？因为这样一来，初始时，对于起点 l，被标记的子串数量就是 $n - (n+1) + 1 = 0$ 个，非常合理！

现在，我们的算法就清晰了喵~

创建一个数组 min_r，大小为 $n+1$ ，所有元素都初始化为 $n+1$ 。
创建一个变量 total_marked_count，初始化为 0，用来记录总的标记数量。
对于每一个查询 (l, r)： a. 我们找到 min_r[l]，这是之前对于起点 l 的最小右边界，我们叫它 old_min_r。 b. 如果新的 r 比 old_min_r 还要小，说明我们找到了一个更强的约束！ i. 新的最小右边界 new_min_r 就变成了 r。 ii. 之前，以 l 为起点的被标记子串有 $n - old\_min\_r + 1$ 个。 iii. 现在，以 l 为起点的被标记子串有 $n - new\_min\_r + 1$ 个。 iv. 那么，新增加的被标记子串数量就是 $(n - new\_min\_r + 1) - (n - old\_min\_r + 1) = old\_min\_r - new\_min\_r$ 。 v. 我们把这个增量加到 total_marked_count 上。 vi. 最后，不要忘记更新 min_r[l] = new_min_r。 c. 如果新的 r 不比 old_min_r 小，那什么都不会发生，总数也不变。
每次查询后，输出 total_marked_count 就好啦！

最有趣的是，自始至终我们都没有用到字符串 s 的具体内容！这真是一道伪装成字符串题的思维计数题呢，喵~

代码实现

这是我根据上面的思路，精心为你准备的代码哦~

cpp

#include <iostream>
#include <vector>
#include <string>
#include <numeric>
#include <algorithm>

// 为了让代码更清晰，我们把核心逻辑放到一个函数里喵~
void solve() {
    int n; // 字符串长度
    int q; // 查询次数
    std::cin >> n >> q;
    
    // 字符串s其实用不到，但题目输入了，我们还是要读一下的，喵~
    std::string s;
    std::cin >> s;

    // total_marked_count 可能会很大，所以用 long long 才安全哦
    long long total_marked_count = 0;
    
    // min_right_boundary[l] 存储对于起点 l，所有查询中最小的 r
    // 我们使用 1-based 索引，所以数组大小是 n + 1
    // 初始化为 n + 1 是个小技巧，代表初始时没有子串被标记
    // (因为 n - (n+1) + 1 = 0)
    std::vector<int> min_right_boundary(n + 1, n + 1);

    for (int i = 0; i < q; ++i) {
        int l, r;
        std::cin >> l >> r;

        // 获取当前起点 l 对应的最小右边界
        int old_min_r = min_right_boundary[l];

        // 如果新的 r 比我们记录的最小 r 还要小，说明可以标记更多子串
        if (r < old_min_r) {
            // 新增的被标记子串数量就是 old_min_r 和新 r 之间的差值
            long long increment = old_min_r - r;
            total_marked_count += increment;
            
            // 更新起点 l 的最小右边界
            min_right_boundary[l] = r;
        }

        // 每次查询后输出当前的累计总数
        std::cout << total_marked_count << "\n";
    }
}

int main() {
    // 加速输入输出，让程序跑得像猫一样快，喵~
    std::ios_base::sync_with_stdio(false);
    std::cin.tie(NULL);

    solve();

    return 0;
}

复杂度分析

时间复杂度: $O(N + Q)$
- 初始化 min_right_boundary 数组需要 $O(N)$ 的时间。
- 我们有 $Q$ 次查询，每次查询内部只进行几次常数时间的读写和计算操作。所以处理所有查询需要 $O(Q)$ 的时间。
- 总的时间复杂度就是 $O(N + Q)$ ，非常高效！
空间复杂度: $O(N)$
- 我们主要使用了一个 min_right_boundary 数组来存储每个起点的状态，它的大小是 $N+1$ 。所以空间复杂度是 $O(N)$ 。

知识点总结

这道题虽然简单，但背后的小思想很有趣，值得我们学习和总结，喵~

问题转化: 核心在于将一个看似复杂的“标记字符串前缀”问题，转化为一个简单的“更新区间最小值”的计数问题。识别出问题本质，剥离无关信息（比如字符串的具体内容）是解题的关键一步。
独立性: 意识到不同起点的子串是相互独立的，可以分开处理，这是简化问题的突破口。很多复杂问题都可以通过拆分成若干个独立的子问题来解决。
增量思想: 我们不是每次都重新计算总数，而是通过计算每次操作带来的“增量”来更新总数。这是一种非常重要的优化思想，在动态规划、数据结构等领域随处可见。
巧妙的初始化: 将 min_r 数组初始化为 $n+1$ 使得第一次查询和后续查询的逻辑可以统一处理，避免了 if-else 的繁琐判断，让代码更简洁优雅。

希望这篇题解能帮到你，如果还有问题，随时可以再来问我哦，喵~

辞书 - 题解 ​

标签与难度 ​

题目大意喵~ ​

解题思路分析 ​

代码实现 ​

复杂度分析 ​