洛谷P1383「IOI 2012」《高级打字机》

IOI 也出板子题?

题目描述

早苗入手了最新的高级打字机。最新款自然有着与以往不同的功能,那就是它具备撤销功能,厉害吧。

请为这种高级打字机设计一个程序,支持如下3种操作:

1.T x:在文章末尾打下一个小写字母x。(type操作)

2.U x:撤销最后的x次修改操作。(Undo操作)

(注意Query操作并不算修改操作)

3.Q x:询问当前文章中第x个字母并输出。(Query操作)

文章一开始可以视为空串。

输入格式

第1行:一个整数n,表示操作数量。

以下n行,每行一个命令。保证输入的命令合法。

输出格式

每行输出一个字母,表示Query操作的答案。

输入输出样例

输入 #1

1
2
3
4
5
6
7
8
7
T a
T b
T c
Q 2
U 2
T c
Q 2

输出 #1

1
2
b
c

说明/提示

【数据范围】

对于40%的数据 n<=200;

对于100%的数据 n<=100000;保证Undo操作不会撤销Undo操作。

<高级挑战>

对于200%的数据 n<=100000;Undo操作可以撤销Undo操作。

必须使用在线算法完成该题。

解析

普通数据

就是个模拟。。。没啥好讲的

代码之后会给

IOI 挑战

原题为 IOI2012 Scrivener PDF 链接

这不就是个可持久化数组板子吗。。。
就这还 IOI 题?


算了还是好好说一下三种操作吧

  1. 插入操作
    提前开好一个大小为 n 的可持久化数组,每次插入的时候建一个新的版本,把上个版本的长度 + 1 处字符修改了就好
  2. 撤销操作
    直接新开一个版本,把版本信息(根节点和长度)修改成撤销到的那个版本就行了
  3. 查询操作
    这个就是模板操作了,不再赘述

什么?听说你不会可持久化数据结构?
不久之后我会专门开一篇讲的

代码实现

普通数据

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
#include <cstdio>

const int MAXN = 100000 + 10;

int n, ptr;
char ss[MAXN];

int main() {
scanf("%d", &n);
while (n --> 0) {
char op[3], a[3];
int x;
scanf("%s", op);
if (op[0] == 'T') {
scanf("%s", a);
ss[++ptr] = a[0];
} else if (op[0] == 'U') {
scanf("%d", &x);
ptr -= x;
} else {
scanf("%d", &x);
printf("%c\n", ss[x]);
}
}
return 0;
}

IOI 挑战

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
#include <cstdio>

const int MAXN = 100000 + 10;

struct Node {
int ls, rs; char val;
Node(int _ls = 0, int _rs = 0, char _val = 0) { ls = _ls; rs = _rs; val = _val; }
} tree[MAXN << 5]; int cnt;

int n, roots[MAXN << 5], lens[MAXN << 5], version;

void modify(int &root, int base, int l, int r, int pos, char val) {
root = ++cnt; tree[root] = tree[base];
if (l == r) return (void) (tree[root].val = val);
int mid = (l + r) >> 1;
if (pos <= mid) modify(tree[root].ls, tree[base].ls, l, mid, pos, val);
else modify(tree[root].rs, tree[base].rs, mid + 1, r, pos, val);
}

char query(int root, int l, int r, int pos) {
if (l == r) return tree[root].val;
int mid = (l + r) >> 1;
if (pos <= mid) return query(tree[root].ls, l, mid, pos);
else return query(tree[root].rs, mid + 1, r, pos);
}

int main() {
scanf("%d", &n);
for (int i = 1; i <= n; ++i) {
char cmd[3];
scanf("%s", cmd);
if (cmd[0] == 'T') {
++version; lens[version] = lens[version - 1] + 1;
char sss[3]; scanf("%s", sss);
modify(roots[version], roots[version - 1], 1, n, lens[version], sss[0]);
} else if (cmd[0] == 'U') {
int ver; scanf("%d", &ver);
++version; roots[version] = roots[version - ver - 1];
lens[version] = lens[version - ver - 1];
} else {
int pos; scanf("%d", &pos);
printf("%c\n", query(roots[version], 1, n, pos));
}
}
return 0;
}