NC15975 小C的记事本 栈 暴力模拟

链接：https://ac.nowcoder.com/acm/problem/15975
来源：牛客网

题目描述
小C最近学会了java小程序的开发，他很开心，于是想做一个简单的记事本程序练练手。

他希望他的记事本包含以下功能：

1、append(str)，向记事本插入字符串 str（英文字符）

2、delete(k)，删除记事本最后k个字符（保证不为空串）

3、print(k)，输出记事本第k个字符（保证不为空串）

4、undo()，撤销最近的1（或者）操作，使记事本回到1（或者2）操作之前的状态

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

多组输入

第一行输入一个整数q，代表操作总数

以下q行每行描述了一个操作，每行以一个整数t开始（1 <= t <= 4）。

t表示上述问题陈述中定义的操作类型。 如果操作需要参数，则后跟空格分隔的参数。

题目保证所有操作均合法

1 <= q <= 10^6
1 <= k <= |记事本内容长度|
每个测试数据中str的总长度 <= 10^6

请使用 ios::sync_with_stdio(false); 对读写进行加速

输出描述:

所有操作类型3必须输出第k个字符，每行以换行符结束。

示例1
输入
复制

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

输出
复制

b
c
a

说明

样例解释

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

1、插入ab，S=“ab”

2、输出第2个字符，是b

3、删除最后2个字符，S=""

4、插入cd, S=“cd”

5、输出第1个字符，是c

6、撤销，此时S=""

7、撤销，此时S=“ab”

8、输出第1个字符，是a

想了半天没想出来如何撤销,看了别人的代码才知道是用栈存储每一步操作,
撤销就是出栈, 虽然感觉内存开销有点大,但是能AC就够笑一整天了

#define debug
#ifdef debug
#include <time.h>
#include "/home/majiao/mb.h"
#endif

#include <iostream>
#include <algorithm>
#include <vector>
#include <string.h>
#include <map>
#include <set>
#include <stack>
#include <queue>
#include <math.h>

#define MAXN ((int)1e6+7)
#define ll long long int
#define INF (0x7f7f7f7f)
#define fori(lef, rig) for(int i=lef; i<=rig; i++)
#define forj(lef, rig) for(int j=lef; j<=rig; j++)
#define fork(lef, rig) for(int k=lef; k<=rig; k++)
#define QAQ (0)

using namespace std;

#ifdef debug
#define show(x...) \ do { \ cout << "\033[31;1m " << #x << " -> "; \ err(x); \ } while (0)

void err() { cout << "\033[39;0m" << endl; }
template<typename T, typename... A>
void err(T a, A... x) { cout << a << ' '; err(x...); }
#endif

#ifndef debug
namespace FIO {
	template <typename T>
	void read(T& x) {
		int f = 1; x = 0;
		char ch = getchar();

		while (ch < '0' || ch > '9') 
			{ if (ch == '-') f = -1; ch = getchar(); }
		while (ch >= '0' && ch <= '9') 
			{ x = x * 10 + ch - '0'; ch = getchar(); }
		x *= f;
	}
};
using namespace FIO;
#endif


int n, m, Q, K;
char buf[MAXN];

#define TOP (stk.top())

int main() {
#ifdef debug
	freopen("test", "r", stdin);
	clock_t stime = clock();
#endif
#if 1
	while(~scanf("%d ", &Q)) {
		stack<string> stk;
		stk.push("");
		while(Q--) {
			int op;
			scanf("%d ", &op);
			if(op == 1) {
				scanf("%s ", buf);
				string s = TOP + buf;
				stk.push(s);
			} else if(op == 2) {
				scanf("%d ", &K);
				string s = TOP.substr(0, TOP.size()-K);
				stk.push(s);
			} else if(op == 3) {
				scanf("%d ", &K);
				K --;
				printf("%c\n", TOP[K]);
			} else {
				if(stk.size() > 1) stk.pop();
			}
		}
	}
#else 
	string s = "0123456";
	cout << s.substr(0, 7-3);
#endif




#ifdef debug
	clock_t etime = clock();
	printf("rum time: %lf 秒\n",(double) (etime-stime)/CLOCKS_PER_SEC);
#endif 
	return 0;
}