【栈】-----【小C的记事本】

小C的记事本

题目描述

小C最近学会了 Java 小程序的开发，他很开心，于是想做一个简单的记事本程序练练手。
他希望他的记事本包含以下功能：

1. append(str)：向记事本插入字符串 str（英文字符）。
2. delete(k)：删除记事本最后 k 个字符（保证不为空串）。
3. print(k)：输出记事本第 k 个字符（保证不为空串）。
4. undo()：撤销最近的 append 或 delete 操作，使记事本回到该操作之前的状态。

可怜的小C琢磨了半天还是做不来，聪明的你能解决小C的问题吗？

输入描述

• 多组输入。

• 每组输入第一行是一个整数 q，代表操作总数。

• 接下来 q 行每行描述一个操作，每行以一个整数 t 开头$（1\le t\le 4）$：

  • 若操作需要参数，则在 t 后用空格分隔给出参数。

• 题目保证所有操作均合法

• 约束条件：

  • 1 ≤ q ≤ $10^6$
  • 每个测试数据中所有 append 的 $字符串总长度$ $\le$ $10^6$

• 提示：请使用 ios::sync_with_stdio(false); 等手段对读写进行加速。

输出描述

• 对于每个 print(k) 操作，输出记事本当前状态下第 k 个字符，每个输出后换行。

示例

输入

8
1 ab
3 2
2 2
1 cd
3 1
4
4
3 1

输出

b
c
a

样例解释

假设记事本内容用字符串 S 表示：

1. 操作 1 ab：插入 "ab"，此时 S = "ab".
2. 操作 3 2：输出第 2 个字符，是 b.
3. 操作 2 2：删除最后 2 个字符，S = "".
4. 操作 1 cd：插入 "cd"，S = "cd".
5. 操作 3 1：输出第 1 个字符，是 c.
6. 操作 4：撤销，上一次是 append("cd")，撤销后 S = "".
7. 操作 4：再撤销，上一次是删除操作，撤销后 S = "ab".
8. 操作 3 1：输出第 1 个字符，是 a.

#include <bits/stdc++.h>
using namespace std;

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

    int q;
    // 支持多组输入：当能读入 q 时就处理一组
    while (cin >> q) 
    {
        // 当前文本内容，初始为空
        string S;
        S.reserve(1000000);  // 预留，避免多次扩容

        // 操作历史栈：pair.first 表示操作类型（1=append, 2=delete），
        // pair.second 存储对应的字符串（append 时存被添加的 str，delete 时存被删除的部分）
        stack<pair<int, string>> history;
        
        while (q--) 
        {
            int t;
            cin >> t;
            
            if (t == 1) 
            {
                // append(str)
                string str;
                cin >> str;
                // 将 str 追加到 S 末尾
                S += str;
                // 记录这次 append 操作及内容，以便 undo 时删除
                history.push({1, str});
            }
            else if (t == 2) 
            {
                // delete(k)
                int k;
                cin >> k;
                // 取出要删除的末尾 k 个字符
                // 注意题目保证 k <= |S|
                string removed = S.substr(S.size() - k);
                // 删除末尾 k 个字符
                S.resize(S.size() - k);
                // 记录这次 delete 操作及被删除的内容，以便 undo 时恢复
                history.push({2, removed});
            }
            else if (t == 3) {
                // print(k)
                int k;
                cin >> k;
                // 题目保证 1 <= k <= |S|
                // 输出第 k 个字符，下标从 1 开始
                cout << S[k - 1] << '\n';
            }
            else if (t == 4) {
                // undo()
                if (!history.empty()) {
                    auto p = history.top();
                    history.pop();
                    if (p.first == 1) {
                        // 撤销 append：删掉上次 append 的内容长度
                        int len = (int)p.second.size();
                        // 题目保证之前 append 的内容确实在末尾
                        S.resize(S.size() - len);
                    } else {
                        // 撤销 delete：恢复上次 delete 时删除的内容
                        // 把被删除的字符串重新追加到末尾
                        S += p.second;
                    }
                }
            }
            // 题目保证输入的 t 只会是 1~4，且操作合法，不必额外 else 分支
        }
        // 处理完一组后，如果有多组，则继续 next while(cin>>q)
    }

    return 0;
}

详细题解后续更新