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

十一月 02, 2019 3209

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挑战>

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

解析

普通数据

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

代码之后会给

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