题解
16 分钟 读完 (大约 2406 个字) 0次访问

NOI2003 - 文本编辑器

【LuoguP4008】【BZOJ1507】【NOI2003】文本编辑器 Editor
题目链接1: https://www.luogu.org/problemnew/show/P4008
题目链接2: https://www.lydsy.com/JudgeOnline/problem.php?id=1507

前言

这题放在任务计划里已经有些时日了，又拿出来看了看题面。原本是练习Splay用的，但因为不够熟练和懒得缘故，一直不想动手写。看了题解，发现了一个思路简单，代码较为暴力的数据结构——“块状链表”。

然后就愉快的做（抄）完了，首先感谢@HenryHuang的题解，他的题解使我学习块状链表得到了很大帮助。

我才不会告诉你很久以前我以为这是STL中string的练手题。

分析

首先这道题有一个光标，只需用一个变量就可以维护光标。

然后就只剩下Insert、Delete、Get操作了，一般我们都会想到平衡树（Splay），但是难理解且代码复杂。

首先我们都听说过甚至用过链表，STL中的list就是使用链表实现。这种数据结构只能$ O(1) $获得首节点和尾结点，需要逐个遍历才能获得中间的节点。

不过链表也有优点，由于它的结构为一条链，每个节点维护了前节点指针和后节点指针，因此向中间插入一个数的复杂度为$ O(1) $。

然而对于这道题，使用链表并不可行，数据范围太大。

还有一个最简单最常见的数据结构，名叫数组。这个数据结构支持$ O(1) $访问。STL中有封装好的类数组数据结构vector，其中有封装好的函数insert用来插入操作。

对于数组，插入操作只需要2次memcpy函数，一次赋值操作就能完成，但是复杂度是极高的。每次插入的理论最大复杂度是 $ O(\frac{n}{2}) $

那么这题就不能投机取巧了吗？万一把数组和链表通过一定方式结合起来，复杂度不就会均衡了吗？

众所周知，优化暴力的方法有很多，其中分块（根号）算法就非常热门。那么我们让数组的大小$ \sqrt{n} $，然后将这些数组通过链表链接起来，那复杂度不就均衡了吗。

这种数据结构就是我使用的——块状链表。首先是定义一个结构体，用来存储某一节点的信息。我们只需要维护一个指向下一元素指针即可。

题目中说明了最大数据范围：

所有 INSERT 插入的字符数之和不超过 2M（1M=1024*1024 字节） ，正确的输出文件长度不超过 3M 字节。

所以我设置每个块的大小为1300，其实块大小在一定范围内即可。在这范围内，块大小和效率只有微小的关系。

1
2
3
4
5
const int sqrtn= 1300;
struct BLOCK {
	int siz, nxt;
	char ch[sqrtn << 1];
} b[sqrtn << 2];

内存池

为了节点数组循环利用，学习原题解的做法，使用内存池。注意，程序开始时需要初始化内存池。

1
2
3
4
5
6
7
8
int blocks[sqrtn << 2], bp, cur;
inline int newb() {
	return blocks[bp++];
}
inline void delb(int x) {
	blocks[--bp]= x;
	return;
}

肯定会有人问，块状链表怎么维护呢？这是最核心的部分。

Split

当某一个块较大时我们需要分裂成两个块。在某些操作（插入、删除等）时，我们可以先从光标位置分裂这个块，然后就可以很方便的对后面的内容进行操作。

1
2
3
4
5
6
7
// x 代表块编号，p代表分裂的位置（相对于块x）
void split(int x, int p) {
	if(x == -1 || p == b[x].siz) return;
	add(x, newb(), b[x].ch + p, b[x].siz - p);
	b[x].siz= p;
	return;
}

Add

上面的split函数中用到了add，这个函数是用来在某一块后面插入一个块。但add函数用作插入，那样就不能维护块状链表的性质了。

add函数与链表的插入类似，只不过赋值变成了memcpy函数。

1
2
3
4
5
6
7
8
9
// x 代表块编号
// y 常为一个未初始的块
// st 为块 y 中的内容
// siz 为 st 的长度
inline void add(int x, int y, char *st, int siz) {
	if(y != -1) b[y].nxt= b[x].nxt, b[y].siz= siz, memcpy(b[y].ch, st, siz);
	b[x].nxt= y;
	return;
}

Merge

如果两个相邻的块都很小，那么维护时就要需要合并。我选择将靠后的块合并到靠前的块中，这样比较简单。

1
2
3
4
5
6
7
// x 代表块的编号
// y 代表合并到 x 的块的编号
void merge(int x, int y) {
	memcpy(b[x].ch + b[x].siz, b[y].ch, b[y].siz);
	b[x].siz+= b[y].siz, b[x].nxt= b[y].nxt, delb(y);
	return;
}

何时维护

其实我学习的时候，一开始也对维护有些不解。虽然知道了如何维护，但没有具体的思路，不知道什么时候需要维护。

根据前人的题解，维护只需要部分维护，即在插入和删除操作之后，维护相关的块。只要保证相邻两块大小之和大于$ \sqrt{n} $，每块大小不超过$ \sqrt{n} $，并且不考虑当块较大时的分裂操作，可以保证块的数量控制在 $ [\sqrt{n},\sqrt{2n}] $ 范围内。

这里再次感谢@HenryHuang的题解所给予的帮助。

对于本题

本题中有插入和删除操作，两者类似。先得到光标当前所属的块，将此块在光标位置分裂。

对于插入，N 代表要插入的字符串长度。我们在分裂的位置先插入$ \frac{N}{\sqrt{n}} $个长度为$ \sqrt{n} $的块，剩下不足$ \sqrt{n} $长度的再独自插入，因为思路简单就不做解释。然后判断大小合并分裂位置前的块$ x $与$ x $的next块，合并刚插入的最后一个块$ y $与$ y $的next块。

对于删除，N 代表要删除的长度。在分裂的位置后逐个删除回收即可，如果最后一个块的长度大于剩余删除数，就再次分裂最后一个块，然后删除。

这部分代码将最后给出，先给出遍历块查找当前光标位置的代码。

1
2
3
4
5
6
7
// x 为要找的位置，
// 因为 x 也是一个引用，最后将赋值为相对于块res的位置
inline int pos(int &x) {
	int res= 0;
	while(res != -1 && b[res].siz < x) x-= b[res].siz, res= b[res].nxt;
	return res;
}

对于Get操作更简单，不需要分裂操作，我为了方便直接在函数中输出了。推荐学习者自行构思，有助于对块状链表的理解。

提示，此题读入较大，建议使用极速IO优化。

代码

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
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
#include <iostream>
#include <stdio.h>
#include <string.h>
using namespace std;
struct IOBUF {
	struct {
		char buff[1 << 24], *p, *pend;
	} in;
	struct {
		char buff[1 << 24], *p;
	} out;
	IOBUF() {
		in.p= in.buff, out.p= out.buff, in.pend= in.buff + fread(in.buff, 1, 1 << 24, stdin);
	}
	~IOBUF() {
		fwrite(out.buff, 1, out.p - out.buff, stdout);
	}
} IOB;
#define getchar() (*(IOB.in.p++))
#define putchar(c) (*(IOB.out.p++)= (c))
int read() {
	int e= 0;
	char ch= getchar();
	while(ch < '0' || ch > '9') ch= getchar();
	while(ch >= '0' && ch <= '9') e= e * 10 + ch - '0', ch= getchar();
	return e;
}
const int sqrtn= 1300;
struct BLOCK {
	int siz, nxt;
	char ch[sqrtn << 1];
} b[sqrtn << 2];
int blocks[sqrtn << 2], bp, cur;
inline void init() {
	for(int i= 1; i < (sqrtn << 2); i++) blocks[i]= i;
	b[0].nxt= -1, bp= 1;
	return;
}
inline int newb() {
	return blocks[bp++];
}
inline void delb(int x) {
	blocks[--bp]= x;
	return;
}
inline void add(int x, int y, char *st, int siz) {
	if(y != -1) b[y].nxt= b[x].nxt, b[y].siz= siz, memcpy(b[y].ch, st, siz);
	b[x].nxt= y;
	return;
}
inline int pos(int &x) {
	// &x
	int res= 0;
	while(res != -1 && b[res].siz < x) x-= b[res].siz, res= b[res].nxt;
	return res;
}
void split(int x, int p) {
	if(x == -1 || p == b[x].siz) return;
	add(x, newb(), b[x].ch + p, b[x].siz - p);
	b[x].siz= p;
	return;
}
void merge(int x, int y) {
	memcpy(b[x].ch + b[x].siz, b[y].ch, b[y].siz);
	b[x].siz+= b[y].siz, b[x].nxt= b[y].nxt, delb(y);
	return;
}
void insert(int w, int siz, char *st) {
	int nowp= pos(w);
	split(nowp, w);
	int nextp, fp= nowp;
	while(sqrtn < siz) {
		nextp= newb();
		add(nowp, nextp, st, sqrtn);
		st+= sqrtn, siz-= sqrtn, nowp= nextp;
	}
	nextp= newb(), add(nowp, nextp, st, siz);
	if(b[nextp].nxt != -1 && b[nextp].siz + b[b[nextp].nxt].siz < sqrtn) merge(nextp, b[nextp].nxt);
	if(b[fp].nxt != -1 && b[fp].siz + b[b[fp].nxt].siz < sqrtn) merge(fp, b[fp].nxt);
	return;
}
void erase(int w, int siz) {
	int nowp= pos(w);
	split(nowp, w);
	int nextp= b[nowp].nxt;
	while(siz > b[nextp].siz) siz-= b[nextp].siz, b[nowp].nxt= b[nextp].nxt, delb(nextp), nextp= b[nowp].nxt;
	split(nextp, siz), b[nowp].nxt= b[nextp].nxt, delb(nextp);
	while(b[nowp].nxt != -1 && b[nowp].siz + b[b[nowp].nxt].siz < sqrtn) merge(nowp, b[nowp].nxt);
	return;
}
void get(int w, int siz) {
	int nowp= pos(w), mins;
	mins= min(siz, b[nowp].siz - w), siz-= mins;
	for(int i= w; i < w + mins; i++) putchar(b[nowp].ch[i]);
	while(siz) {
		nowp= b[nowp].nxt, mins= min(siz, b[nowp].siz), siz-= mins;
		for(int i= 0; i < mins; i++) putchar(b[nowp].ch[i]);
	}
	putchar('\n');
	return;
}
char readopt() {
	char ch= getchar();
	while(ch != 'M' && ch != 'I' && ch != 'D' && ch != 'G' && ch != 'P' && ch != 'N') ch= getchar();
	return ch;
}
int m, n;
char str[1048576];
int main() {
	init(), m= read();
	while(m--) {
		switch(readopt()) {
			case 'M': cur= read(); break;
			case 'P': --cur; break;
			case 'N': ++cur; break;
			case 'I': {
				n= read();
				for(int i= 0; i < n; i++) {
					str[i]= getchar();
					if(str[i] < 32 || str[i] > 126) --i;
				}
				insert(cur, n, str);
				break;
			}
			case 'D': {
				n= read();
				erase(cur, n);
				break;
			}
			case 'G': {
				n= read();
				get(cur, n);
				break;
			}
			default: break;
		}
	}
	return 0;
}
# , , ,
技巧 - 在OJ上出交互题
LuoguP3396 - 哈希冲突

评论

关注我

链接

分类

标签云

Cpp GCD HTML JavaScript LCA STL ST表 alpha-beta剪枝 主席树 二分查找 分块 前缀和 动态规划 块状链表 字典树 字符串 左偏树 并查集 技巧 搜索 数论 整除分块 模拟 比赛 爬虫 状压DP 码风 离散化 粤语 线段树 背包 莫比乌斯反演 莫队 解释器 记忆 记忆化搜索 语录 边压Trie 闲聊 随机化搜索 项目 颓废 题解

最新文章

归档

标签

Cpp 29
GCD 1
HTML 1
JavaScript 1
LCA 1
STL 2
ST表 1
alpha-beta剪枝 1
主席树 1
二分查找 1
分块 3
前缀和 1
动态规划 5
块状链表 1
字典树 1
字符串 1
左偏树 1
并查集 2
技巧 3
搜索 6
数论 1
整除分块 1
模拟 4
比赛 1
爬虫 3
状压DP 2
码风 1
离散化 1
粤语 1
线段树 1
背包 1
莫比乌斯反演 1
莫队 1
解释器 1
记忆 1
记忆化搜索 1
语录 1
边压Trie 1
闲聊 7
随机化搜索 2
项目 3
颓废 6
题解 22

最新文章

归档

标签

Cpp 29
GCD 1
HTML 1
JavaScript 1
LCA 1
STL 2
ST表 1
alpha-beta剪枝 1
主席树 1
二分查找 1
分块 3
前缀和 1
动态规划 5
块状链表 1
字典树 1
字符串 1
左偏树 1
并查集 2
技巧 3
搜索 6
数论 1
整除分块 1
模拟 4
比赛 1
爬虫 3
状压DP 2
码风 1
离散化 1
粤语 1
线段树 1
背包 1
莫比乌斯反演 1
莫队 1
解释器 1
记忆 1
记忆化搜索 1
语录 1
边压Trie 1
闲聊 7
随机化搜索 2
项目 3
颓废 6
题解 22
Your browser is out-of-date!

Update your browser to view this website correctly. Update my browser now

×