NOI2003文本编辑器

Posted on |

problem

传送门

Solution

块状链表板子题……

码了一下午，调了一晚上，代码重构了3遍，在终于过了。

还是太菜了。

移动光标的操作直接模拟即可。

插入操作，先将光标所在块分裂成两块，然后直接插入。

删除操作直接将边角料变成新块，然后相互连接。

细节有点多……

第一次打，代码奇丑，而且没有优化空间……

算了，以后在填坑吧……

Code

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
#include <bits/stdc++.h>

using namespace std;

#define DEBUG(...) fprintf(stderr, __VA_ARGS__)
#define mp make_pair
#define fst first
#define snd second

template<typename T> inline bool chkmin(T &a, const T &b) { return a > b ? a = b, 1 : 0; }
template<typename T> inline bool chkmax(T &a, const T &b) { return a < b ? a = b, 1 : 0; }

inline int read(){
	int res = 0, fl = 1;
	char r = getchar();
	for (; !isdigit(r); r = getchar()) if(r == '-') fl = -1;
	for (; isdigit(r); r = getchar()) res = (res << 3) + (res << 1) + r - 48;
	return res * fl;
}
typedef long long LL;
typedef pair<int, int> pii;

const int Maxl = 1024 * 1024 * 2, siz = Maxl / 500, blk = Maxl / siz;
char ch[Maxl + 10];
int cnt;

struct node {
	int lst, nxt, len;
	short c[blk + 10];
	void putout(){ for (int i = 1; i <= len; ++i) putchar(c[i]);}
	void back(int C){ c[++len] = C;}
}B[siz << 6];
void check(){
	for (int id = 1; B[id].nxt; id = B[id].nxt){
		if(B[B[id].nxt].len + B[id].len <= blk){
			for (int i = 1; i <= B[B[id].nxt].len; ++i)
				B[id].back(B[B[id].nxt].c[i]);
			B[id].nxt = B[B[id].nxt].nxt;
			B[B[id].nxt].lst = id;
		}
	}
}
int find(int cur, int &Id){
	for (Id = 1; Id && cur > B[Id].len; Id = B[Id].nxt) cur -= B[Id].len;
	return cur;
}
void MakeBlock(int len,int Lst){
	int num = 1;
	B[++cnt].lst = Lst;
	B[Lst].nxt = cnt;
	for (int i = 1; i <= len; ++i){
		if(num * blk + 1 == i){
			B[cnt].nxt = cnt + 1;
			cnt++, num++;
			B[cnt].lst = cnt - 1;
		}
		B[cnt].back(ch[i]);
	}
}
char tmp[5000];
void Insert(int cur, int len){
	int Id;
	cur = find(cur, Id);
	int Nxt = B[Id].nxt, Lst = B[Id].lst;
	MakeBlock(len, Id);
	for (int i = 1; i <= B[Id].len - cur; ++i) ch[i] = B[Id].c[cur + i];
	MakeBlock(B[Id].len - cur, cnt);
	B[cnt].nxt = Nxt;
	B[Nxt].lst = cnt;
	B[Id].len = cur;
	check();
}
void put_out(int cur,int len){
	int Bid, Eid, ecur;
	ecur = find(cur + len, Eid);
	cur = find(cur, Bid);
	if(Bid == Eid){
		for (int i = cur + 1; i <= ecur; ++i) putchar(B[Bid].c[i]);
		putchar('\n');
		return;
	}
	for (int i = cur + 1; i <= B[Bid].len; ++i)putchar(B[Bid].c[i]);
	for (Bid = B[Bid].nxt; Bid != Eid; Bid = B[Bid].nxt)B[Bid].putout();
	for (int i = 1; i <= ecur; ++i) putchar(B[Bid].c[i]);
	putchar('\n');
}
void Erase(int cur, int len){
	int Bid, Eid, ecur;
	ecur = find(cur + len, Eid);
	cur = find(cur, Bid);
	if(Bid == Eid){
		int xz = 0;
		for (int i = 1; i <= cur; ++i) ch[++xz] = B[Bid].c[i];
		for (int i = ecur + 1; i <= B[Bid].len; ++i) ch[++xz] = B[Bid].c[i];
		for (int i = 1; i <= xz; ++i) B[Bid].c[i] = ch[i];
		B[Bid].len = xz;
		check();
		return ;
	}
	B[Bid].len = cur;
	int xz = 0;
	for (int i = ecur + 1; i <= B[Eid].len; ++i) B[Eid].c[++xz] = B[Eid].c[i];
	B[Eid].len = xz;
	B[Bid].nxt = Eid;
	B[Eid].lst = Bid;
	check();
}
int main()
{
#ifndef ONLINE_JUDGE
	freopen("a.in", "r", stdin);
	freopen("a.out", "w", stdout);
#endif
	int t = read(), cur = 0;
	char opt[10];
	MakeBlock(blk, 0);
	while(t--){
		scanf("%s",opt + 1);
		if(opt[1] == 'M') cur = read();
		if(opt[1] == 'P') cur--;
		if(opt[1] == 'N') cur++;
		if(opt[1] == 'D') Erase(cur, read());
		if(opt[1] == 'G') put_out(cur, read());
		if(opt[1] == 'I'){
			int len = read();
			for (int i = 1; i <= len; ++i){
				ch[i] = getchar();
				if(ch[i] < 32 || ch[i] > 126) i--;
			}
			Insert(cur, len);
		}
	}
	return 0;
}