小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;
}

---

詳細題解后續更新