文本编辑器2 - 题解

标签与难度

标签: 数据结构, 栈, 字符串哈希, 前缀和, 对顶栈, 模拟难度: 2000

题目大意喵~

一位名叫小灰灰的同学正在玩一个只支持数字的文本编辑器，喵~ 他会进行 $q$ 次操作，同时小蓝会提出 $m$ 个问题。这些操作和问题是交错进行的。

编辑器有四种操作：

I x: 在光标位置插入一个数字 x，光标移动到 x 之后。
D: 删除光标前的一个数字。
B: 光标向左移动一个位置（Backspace）。
F: 光标向右移动一个位置（Forward）。

小蓝的问题是：

Q pos len: 询问当前文本中，从第 pos 个数字开始，长度为 len 的子串所代表的整数是多少。因为数字可能很大，所以结果需要对 998244353 取模。

我们需要高效地处理这些操作和查询，给出正确的答案，呐。

解题思路分析

这道题的核心是在一个可以动态修改的字符串上，快速地进行查询。如果用普通的数组或者 string 来模拟，每次在中间插入或删除字符，都需要移动大量的元素，时间复杂度会是 $O(N)$ ，面对大量的操作肯定会超时的说！

所以，我们需要一个更聪明的办法来处理光标和文本的修改，喵~

对顶栈模型

一个非常经典的处理这类 "光标在中间移动和修改" 问题的数据结构就是 对顶栈 (Two Stacks) 模型！

想象一下，我们把整个文本序列从光标位置劈开，分成两部分：

左栈 (left_stack): 存放光标左边的所有字符。栈顶的元素就是离光标最近的那个字符。
右栈 (right_stack): 存放光标右边的所有字符。为了方便操作，我们把右边的字符倒序存入。这样，栈顶的元素也是离光标最近的那个字符。

用这个模型，我们来看看各种操作会发生什么：

I x (插入): 直接把新数字 x 压入 left_stack。时间复杂度 $O(1)$ 。
D (删除): 从 left_stack 弹出一个元素。时间复杂度 $O(1)$ 。
B (光标左移): 从 left_stack 弹出一个元素，然后压入 right_stack。时间复杂度 $O(1)$ 。
F (光标右移): 从 right_stack 弹出一个元素，然后压入 left_stack。时间复杂度 $O(1)$ 。

哇！所有的编辑操作都变成了 $O(1)$ ，是不是很神奇，喵~

快速查询与字符串哈希

解决了编辑操作的效率问题，接下来就是查询了。查询 Q pos len 要求我们计算一个子串代表的数值。如果每次都从栈里把字符一个个拿出来再计算，那也太慢了。

这种 "查询子串的某个属性" 的问题，通常可以用 前缀和 或哈希来优化。这里我们要计算数值，本质上就是一种特殊的哈希——以 10 为底的哈希。

一个数字字符串 $d_1d_2...d_k$ 的值是 $\sum_{i=1}^{k} d_i \cdot 10^{k-i}$ 。我们可以为 left_stack 和 right_stack 分别维护一个哈希值的前缀和数组。

但是，普通的哈希前缀和在栈顶变化时不好维护。比如，left_stack 的哈希值是 ...((d_1*10 + d_2)*10 + d_3)...，在栈顶压入 d_4 很容易，但是弹出 d_3 就很麻烦了。

这里有一个小技巧，我们可以定义一种特殊的哈希函数：

H(S) = \sum_{i=1}^{k} d_i \cdot 10^{-i} \pmod{P}

其中 $10^{-i}$ 是 $10^i$ 在模 $P$ 意义下的乘法逆元。

这种哈希的好处是，当我们在序列末尾添加一个新字符 $d_{k+1}$ 时，新的哈希值就是 $H(S') = H(S) + d_{k+1} \cdot 10^{-(k+1)}$ 。它只和旧的哈希值有关，更新起来非常方便！这完美契合了栈的 LIFO (后进先出) 特性。

我们可以为 left_stack 和 right_stack 分别维护这样一个哈希值的前缀和数组。

left_hashes[i] 存 left_stack 中前 $i$ 个字符的哈希值。
right_hashes[i] 存 right_stack 中前 $i$ 个字符的哈希值。

处理查询

有了哈希数组，查询就变得简单了。假设查询的区间是 [pos, pos + len - 1]。设 p1 是 left_stack 的大小。

查询区间完全在左边: pos + len - 1 <= p1 子串是 left_stack 的第 pos 到 pos + len - 1 个字符。它的哈希值是 left_hashes[pos+len-1] - left_hashes[pos-1]。这个哈希值等于 $\sum_{k=pos}^{pos+len-1} d_k \cdot 10^{-k}$ 。为了得到真实的数值，我们把它乘以 $10^{pos+len-1}$ ，就能把最低位的 $d_{pos+len-1}$ 的权重变为 $10^0$ ，其他的位次也相应对齐了。所以，值为 (left_hashes[pos+len-1] - left_hashes[pos-1]) * 10^{pos+len-1} \pmod P。
查询区间完全在右边: pos > p1 子串是 right_stack 的第 pos - p1 到 pos + len - 1 - p1 个字符。因为 right_stack 是倒序的，所以它的第 k 个字符对应原文本的第 p1 + k 个字符。计算方法和左边类似，只是索引要做一下转换。值为 (right_hashes[pos+len-1-p1] - right_hashes[pos-1-p1]) * 10^{pos+len-1-p1} \pmod P。
查询区间横跨左右: pos <= p1 < pos + len - 1 我们需要把左右两部分的值算出来再拼起来。
- 左半部分: left_stack 的 pos 到 p1。值为 (left_hashes[p1] - left_hashes[pos-1]) * 10^{p1} \pmod P。
- 右半部分: right_stack 的 1 到 pos + len - 1 - p1。值为 (right_hashes[pos+len-1-p1]) * 10^{pos+len-1-p1} \pmod P。
- 拼接: 左半部分的值 * 10^(右半部分的长度) + 右半部分的值。

这样，所有的查询也可以在 $O(1)$ 的时间内完成了！总的来说，这是一个结合了对顶栈和字符串哈希的非常巧妙的解法，喵~

代码实现

cpp

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

using namespace std;

// 定义一个长整型，方便进行模运算
using ll = long long;

// 模数
const int MOD = 998244353;
// 预计算数组的最大大小，根据题目 q 的范围来定
const int MAX_SIZE = 1000005;

// 预计算 10 的幂和 10 的幂的逆元
vector<ll> pow10(MAX_SIZE);
vector<ll> inv_pow10(MAX_SIZE);

// 快速幂函数，用于计算 a^b % MOD
ll power(ll base, ll exp) {
    ll res = 1;
    base %= MOD;
    while (exp > 0) {
        if (exp % 2 == 1) res = (res * base) % MOD;
        base = (base * base) % MOD;
        exp /= 2;
    }
    return res;
}

// 计算 a 在模 MOD 下的乘法逆元
ll modInverse(ll n) {
    return power(n, MOD - 2);
}

// 预计算函数
void precompute() {
    pow10[0] = 1;
    inv_pow10[0] = 1;
    ll inv10 = modInverse(10);
    for (int i = 1; i < MAX_SIZE; ++i) {
        pow10[i] = (pow10[i - 1] * 10) % MOD;
        inv_pow10[i] = (inv_pow10[i - 1] * inv10) % MOD;
    }
}

// 辅助函数，处理取模后的负数情况
ll add(ll a, ll b) {
    return (a + b) % MOD;
}

ll sub(ll a, ll b) {
    return (a - b % MOD + MOD) % MOD;
}

ll mul(ll a, ll b) {
    return (a * b) % MOD;
}

int main() {
    // 优化输入输出，跑得更快喵~
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);

    precompute();

    int q, m;
    cin >> q >> m;
    int total_ops = q + m;

    // 对顶栈模型
    vector<int> left_chars;
    vector<int> right_chars; // 存储的是倒序的右半部分

    // 对应的哈希前缀和数组
    vector<ll> left_hashes(1, 0);
    vector<ll> right_hashes(1, 0);

    for (int k = 0; k < total_ops; ++k) {
        char op;
        cin >> op;

        if (op == 'I') {
            int x;
            cin >> x;
            left_chars.push_back(x);
            // 更新左栈哈希
            ll new_hash = add(left_hashes.back(), mul(x, inv_pow10[left_chars.size()]));
            left_hashes.push_back(new_hash);
        } else if (op == 'D') {
            if (!left_chars.empty()) {
                left_chars.pop_back();
                left_hashes.pop_back();
            }
        } else if (op == 'B') {
            if (!left_chars.empty()) {
                int val = left_chars.back();
                left_chars.pop_back();
                left_hashes.pop_back();

                right_chars.push_back(val);
                // 更新右栈哈希
                ll new_hash = add(right_hashes.back(), mul(val, inv_pow10[right_chars.size()]));
                right_hashes.push_back(new_hash);
            }
        } else if (op == 'F') {
            if (!right_chars.empty()) {
                int val = right_chars.back();
                right_chars.pop_back();
                right_hashes.pop_back();

                left_chars.push_back(val);
                // 更新左栈哈希
                ll new_hash = add(left_hashes.back(), mul(val, inv_pow10[left_chars.size()]));
                left_hashes.push_back(new_hash);
            }
        } else if (op == 'Q') {
            int pos, len;
            cin >> pos >> len;

            int p1 = left_chars.size();
            int end_pos = pos + len - 1;

            ll ans = 0;

            if (end_pos <= p1) { // 区间完全在左边
                ll hash_diff = sub(left_hashes[end_pos], left_hashes[pos - 1]);
                ans = mul(hash_diff, pow10[end_pos]);
            } else if (pos > p1) { // 区间完全在右边
                // 注意右栈是倒序的，所以查询 R_1..R_k 对应的是 right_chars 的末尾 k 个元素
                // 但我们设计的哈希是对正序 R_1, R_2... 计算的，而 right_chars 是 R_k, R_{k-1}...
                // 所以需要反向思考。我们的模型是：
                // left_chars: L_1, ..., L_p1
                // right_chars: R_p2, ..., R_1
                // 对应的文本是 L_1...L_p1 R_1...R_p2
                // 所以对 right_chars 的哈希也应该基于 R_1, R_2... 的顺序
                // B 操作：L_p1 -> R_1; F 操作：R_1 -> L_p1
                // 我们的代码实现里，B 操作是把 L_p1 push_back到 right_chars，所以 right_chars 存的是 R_1, R_2...
                // 这样逻辑就对了！
                int r_start = pos - p1;
                int r_end = end_pos - p1;
                ll hash_diff = sub(right_hashes[r_end], right_hashes[r_start - 1]);
                ans = mul(hash_diff, pow10[r_end]);
            } else { // 区间横跨左右
                // 左半部分: L_pos ... L_p1
                ll left_part_hash_diff = sub(left_hashes[p1], left_hashes[pos - 1]);
                ll left_val = mul(left_part_hash_diff, pow10[p1]);
                
                // 右半部分: R_1 ... R_{end_pos - p1}
                int r_len = end_pos - p1;
                ll right_part_hash_diff = right_hashes[r_len];
                ll right_val = mul(right_part_hash_diff, pow10[r_len]);

                // 拼接
                ans = add(mul(left_val, pow10[r_len]), right_val);
            }
            cout << ans << "\n";
        }
    }

    return 0;
}

复杂度分析

时间复杂度: $O(Q+M)$ 我们首先需要 $O(\text{MaxSize})$ 的时间来预计算 pow10 和 inv_pow10 数组。之后，每一次编辑操作（I, D, B, F）都是 $O(1)$ 的，因为它们只涉及栈顶操作。每一次查询操作（Q）也都是 $O(1)$ 的，因为它只需要从预计算的哈希数组中取出几个值进行计算。所以总时间复杂度是 $O(\text{MaxSize} + Q + M)$ ，在 MaxSize 与 $Q$ 同阶时，可以看作 $O(Q+M)$ 。
空间复杂度: $O(Q)$ 我们需要存储 pow10 和 inv_pow10 数组，空间为 $O(\text{MaxSize})$ 。两个栈以及它们的哈希数组最多会存储 $Q$ 次插入的字符，所以空间复杂度也是 $O(Q)$ 。因此总空间复杂度为 $O(\text{MaxSize} + Q)$ 。

知识点总结

对顶栈 (Two Stacks): 这是解决 "带光标的线性结构" 问题的神器！它能将中间位置的插入和删除操作的复杂度从 $O(N)$ 降到 $O(1)$ 。
字符串哈希: 通过哈希，我们可以将子串的比较或求值问题在 $O(1)$ 时间内完成。
哈希函数的设计: 本题的精髓在于选择了一个巧妙的哈希函数 $H(S) = \sum d_i \cdot 10^{-i}$ ，它能够与栈的 LIFO 特性完美配合，实现 $O(1)$ 的更新。
模块化编程: 将快速幂、求逆元、预计算等功能封装成独立的函数，让主逻辑更清晰，也方便调试和复用，喵~
模块化算术: 在处理大数取模问题时，熟练运用乘法逆元和快速幂是基本功，呐。

希望这篇题解能帮助你理解这道有趣的题目！继续加油哦，喵~

文本编辑器2 - 题解 ​

标签与难度 ​

题目大意喵~ ​

解题思路分析 ​

对顶栈模型 ​

快速查询与字符串哈希 ​

处理查询 ​

代码实现 ​

复杂度分析 ​

知识点总结 ​