【洛谷】P1383 高级打字机

打字机"/>

【洛谷】P1383 高级打字机

题目地址：

题目描述：
早苗入手了最新的高级打字机。最新款自然有着与以往不同的功能，那就是它具备撤销功能，厉害吧。请为这种高级打字机设计一个程序，支持如下 3 3 3种操作：
1.T x：在文章末尾打下一个小写字母 x x x。（Type操作）
2.U x：撤销最后的 x x x次修改操作。（Undo操作）（注意Query操作并不算修改操作）
3.Q x：询问当前文章中第 x x x个字母并输出。（Query 操作）
文章一开始可以视为空串。

输入格式：
第 1 1 1行：一个整数 n n n，表示操作数量。
以下 n n n行，每行一个命令。保证输入的命令合法。

输出格式：
每行输出一个字母，表示Query操作的答案。

数据范围：
对于 40 % 40\% 40%的数据 n ≤ 200 n \le 200 n≤200。
对于 100 % 100\% 100%的数据 n ≤ 100000 n \le 100000 n≤100000；保证Undo操作不会撤销 Undo操作。

高级挑战：
对于 200 % 200\% 200%的数据 n ≤ 100000 n \le 100000 n≤100000；Undo操作可以撤销Undo操作。

IOI挑战：
必须使用在线算法完成该题。

显然要用主席树做。如果撤销操作不会撤销Undo操作，那么只需要将版本回退 x x x步就行了，并且版本号就是字符串的长度（初始版本的版本编号为 0 0 0）。但是由于本题里可能出现撤销操作撤销了之前的撤销操作，所以我们在执行撤销操作的时候，直接开一个新版本，该版本等于 x x x步之前的版本。由于这样失去了每个版本字符串有多长的信息，我们需要另外一个数组记录这个信息。代码如下：

#include <iostream>
using namespace std;const int N = 1e5 + 10;
int n;
struct Node {int l, r;char ch;
} tr[(N << 2) + N * 17];
// root[i]为i号版本的树根下标，len[i]为i号版本的字符串长度，ver为当前版本编号
int root[N], idx, len[N], ver;int build(int l, int r) {int p = ++idx;if (l == r) return p;int mid = l + r >> 1;tr[p].l = build(l, mid), tr[p].r = build(mid + 1, r);return p;
}int update(int p, int l, int r, int k, char ch) {int q = ++idx;tr[q] = tr[p];if (l == r) tr[q].ch = ch;else {int mid = l + r >> 1;if (k <= mid) tr[q].l = update(tr[q].l, l, mid, k, ch);else tr[q].r = update(tr[q].r, mid + 1, r, k, ch);}return q;
}char query(int p, int l, int r, int k) {if (l == r) return tr[p].ch;int mid = l + r >> 1;if (k <= mid) return query(tr[p].l, l, mid, k);else return query(tr[p].r, mid + 1, r, k);
}int main() {cin >> n;for (int i = 1; i <= n; i++) {char op, ch;int x;cin >> op;if (op == 'T') {cin >> ch;ver++;len[ver] = len[ver - 1] + 1;root[ver] = update(root[ver - 1], 1, n, len[ver], ch);} else {cin >> x;if (op == 'U') {// 对于撤销操作，直接开一个新版本，其等同于x步前的版本ver++;root[ver] = root[ver - x - 1];len[ver] = len[ver - x - 1];} else cout << query(root[ver], 1, n, x) << '\n';}}
}

操作 1 1 1和 3 3 3时间复杂度 O ( log ⁡ n ) O(\log n) O(logn)，操作 2 2 2时间 O ( 1 ) O(1) O(1)，空间 O ( n log ⁡ n ) O(n\log n) O(nlogn)。