小C的记事本

题目描述

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

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

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

输入描述

多组输入。
每组输入第一行是一个整数 q，代表操作总数。
接下来 q 行每行描述一个操作，每行以一个整数 t 开头 $\le t \le 4）$ ：
- 若操作需要参数，则在 t 后用空格分隔给出参数。
题目保证所有操作均合法
约束条件：
- 1 ≤ q ≤ $10^6$
- 每个测试数据中所有 append 的 $字符串总长度$ $\le$ $10^6$
提示：请使用 ios::sync_with_stdio(false); 等手段对读写进行加速。

输出描述

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

示例

输入

输出

b
c
a

样例解释

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

操作 1 ab：插入 "ab"，此时 S = "ab".
操作 3 2：输出第 2 个字符，是 b.
操作 2 2：删除最后 2 个字符，S = "".
操作 1 cd：插入 "cd"，S = "cd".
操作 3 1：输出第 1 个字符，是 c.
操作 4：撤销，上一次是 append("cd")，撤销后 S = "".
操作 4：再撤销，上一次是删除操作，撤销后 S = "ab".
操作 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;
}