隐藏
「bsoj5089」文本编辑器 - 双向链表 | Bill Yang's Blog

路终会有尽头，但视野总能看到更远的地方。

0%

「bsoj5089」文本编辑器 - 双向链表

发表于 更新于 分类于 Valine：

题目大意

九发明了一个完美的文本编辑器。这个编辑器拥有两个光标（cursor），所以九能够同时在两处地方插入和删除文本。这个编辑器除了正常的编辑功能以外，还有一些只有九才知道用处的功能，例如翻转两个光标之间的文本。某一天，九把自己的完美文本编辑器给弄丢了，但是她还有好多好多文本需要处理。于是她想请聪明又智慧的你帮她实现完美文本编辑器的一些功能。
功能列表如下：

开始时文本编辑器中有一定内容，左光标在第一个字符左，右光标在最后一个字符右。
注意：在插入和删除操作中，没有被操作的光标与文本的相对左右位置保持不变。特别地，若两个光标重叠，操作后也仍然重叠。

题目分析

当您发现题目中出现了⑨，这道题就已经注定调不出来了。

考试的时候自信满满的打了一棵平衡树，还很快调试出来了，感觉浑身上下散发着AK的气息。（事实证明每当其实RP就会归零）
然后最后成功被卡$\log$，丢掉10分。

平衡树的方法就不用说了吧，下面有代码。

这道题似乎还可以用三个deque来分别维护三段，事后大家都是这么写的？
下面讲讲正解的双向链表。
因为每次仅插入/删除一个字符，因此可以使用双向链表直接修改指针。
当翻转的时候就有点麻烦了，如图：

我们要重新连接端点处的指针，然后将红框内的指针全部翻转。
这里的翻转不能暴力翻转，否则要超时。

在这里就有不同的实现方式了：

  • KEKE_046使用的双向链表没有方向性，因此可以直接无视中间的翻转。
  • achen用标记下传的方式处理翻转

这里讲一下achen的方法：
我们可以暂时不管红框内部的翻转情况，然后对于每一个点的指针进行操作的时候，首先push_down。

push_down的方法是：
若该结点的左指针所指结点的右指针不等于本结点，说明左指针所指结点已经被翻转，指针信息有误，因此翻转左指针。
同样的右指针也做相应的检查。

注意这样标记下传的前提是要从一个信息绝对无误的结点出发才正确，因此从光标开始是不会有错的。

同样这样的标记下传在Show操作的时候还要处理，需要先从光标将所有结点的标记下传一次，然后再进行输出。

代码

90分平衡树

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
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
#include<algorithm>
#include<iostream>
#include<iomanip>
#include<cstring>
#include<cstdlib>
#include<vector>
#include<cstdio>
#include<cmath>
#include<queue>
using namespace std;
inline const int Get_Int() {
	int num=0,bj=1;
	char x=getchar();
	while(x<'0'||x>'9') {
		if(x=='-')bj=-1;
		x=getchar();
	}
	while(x>='0'&&x<='9') {
		num=num*10+x-'0';
		x=getchar();
	}
	return num*bj;
}
const int maxn=6000005;
struct Tree {
	int child[2],father;
	int size;
	char val;
	bool rev,bound;
	Tree(int fa=0,char v='\0',bool b=0):father(fa),val(v),bound(b) {
		child[0]=child[1]=rev=size=0;
	}
};
struct Segment_Splay {
	int root,cnt;
	Tree tree[maxn];
	#define ls(x) tree[x].child[0]
	#define rs(x) tree[x].child[1]
	#define fa(x) tree[x].father
	#define rev(x) tree[x].rev
	#define val(x) tree[x].val
	#define size(x) tree[x].size
	bool checkson(int index) {
		return rs(fa(index))==index;
	}
	void push_up(int index) {
		size(index)=size(ls(index))+size(rs(index))+1;
	}
	void push_down(int index) {
		if(!rev(index))return;
		swap(ls(index),rs(index));
		rev(ls(index))^=1;
		rev(rs(index))^=1;
		rev(index)=0;
	}
	void rotate(int index) {
		int father=fa(index),grand=fa(father);
		push_down(father),push_down(index);
		bool side=checkson(index);
		if(grand)tree[grand].child[checkson(father)]=index;
		tree[father].child[side]=tree[index].child[side^1];
		fa(tree[father].child[side])=father;
		fa(father)=index;
		tree[index].child[side^1]=father;
		fa(index)=grand;
		push_up(father);
		push_up(index);
	}
	void splay(int index,int target=0) {
		for(int father; (father=fa(index))!=target; rotate(index))
			if(fa(father)!=target)push_down(father),rotate(checkson(index)==checkson(father)?father:index);
		if(target==0)root=index;
	}
	int build(int Left,int Right,int father,const char* a) {
		if(Left>Right)return 0;
		int mid=(Left+Right)>>1;
		tree[mid]=Tree(father,a[mid-1]);
		if(Left!=Right) {
			ls(mid)=build(Left,mid-1,mid,a);
			rs(mid)=build(mid+1,Right,mid,a);
		}
		push_up(mid);
		return mid;
	}
	void build(int n,char* a) { //建立并加入哨兵 
		root=build(1,n,0,a);
		cnt=n+2;
		tree[n+1]=Tree(1,'\0',1),ls(1)=n+1,splay(n+1);
		tree[n+2]=Tree(n,'\0',1),rs(n)=n+2,splay(n+2);
	}
	int select(int rank) { //找到第k个数
		int now=root;
		rank++;
		while(true) {
			push_down(now);
			if(ls(now)&&size(ls(now))>=rank)now=ls(now);
			else {
				if(rank==size(ls(now))+1)return now;
				rank-=size(ls(now))+1;
				now=rs(now);
			}
		}
	}
	int split(int Left,int Right) {
		int x=select(Left-1),y=select(Right+1);
		splay(x);
		splay(y,x);
		return ls(y);
	}
	void reverse(int Left,int Right) {
		rev(split(Left,Right))^=1;
	}
	void insert(int pos,char c) {
		int x=select(pos),y=select(pos+1);
		splay(x);
		splay(y,x);
		ls(y)=++cnt;
		tree[cnt]=Tree(y,c);
		push_up(cnt),push_up(y),push_up(x);
	}
	void del(int pos) {
		int x=split(pos,pos);
		int y=fa(x);
		fa(x)=ls(y)=0;
		push_up(y),push_up(fa(y));
	}
	void dfs(int now) {
		if(!now)return;
		push_down(now);
		dfs(ls(now));
		if(!tree[now].bound)printf("%c",val(now));
		dfs(rs(now));
	}
} bbt;
int n,m,L=1,R=1;
char s[4000005];
int main() {
	scanf("%s",s);
	n=strlen(s);
	R=n;
	bbt.build(n,s);
	m=Get_Int();
	for(int i=1; i<=m; i++) {
		char opt=' ';
		while(opt!='<'&&opt!='>'&&opt!='I'&&opt!='D'&&opt!='R'&&opt!='S')opt=getchar();
		if(opt=='<') {
			char w=' ';
			while(w!='L'&&w!='R')w=getchar();
			if(w=='L') {
				if(L>1)L--,puts("T");
				else puts("F");
			} else {
				if(R>0)R--,puts("T");
				else puts("F");
			}
		} else if(opt=='>') {
			char w=' ';
			while(w!='L'&&w!='R')w=getchar();
			if(w=='L') {
				if(L<n+1)L++,puts("T");
				else puts("F");
			} else {
				if(R<n)R++,puts("T");
				else puts("F");
			}
		} else if(opt=='I') {
			char w=' ',v=' ';
			while(w!='L'&&w!='R')w=getchar();
			while(v<33||v>126)v=getchar();
			n++;
			if(w=='L') {
				bbt.insert(L-1,v);
				if(R<L)R--;
			} else {
				bbt.insert(R,v);
				if(L<R)L--;
			}
			L++,R++;
			puts("T");
		} else if(opt=='D') {
			char w=' ';
			while(w!='L'&&w!='R')w=getchar();
			if(w=='L') {
				if(L==n+1)puts("F");
				else {
					if(R>=L)R--;
					bbt.del(L);
					n--;
					puts("T");
				}
			} else {
				if(R==n)puts("F");
				else {
					if(L>=R)L--;
					bbt.del(R+1);
					n--;
					puts("T");
				}
			}
		} else if(opt=='R') {
			if(L>=R)puts("F");
			else {
				bbt.reverse(L,R);
				puts("T");
			}
		} else bbt.dfs(bbt.root);
	}
	return 0;
}

满分双向链表

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
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
#include<algorithm>
#include<iostream>
#include<iomanip>
#include<cstring>
#include<cstdlib>
#include<vector>
#include<cstdio>
#include<cmath>
#include<queue>
using namespace std;
inline const int Get_Int() {
	int num=0,bj=1;
	char x=getchar();
	while(x<'0'||x>'9') {
		if(x=='-')bj=-1;
		x=getchar();
	}
	while(x>='0'&&x<='9') {
		num=num*10+x-'0';
		x=getchar();
	}
	return num*bj;
}
const int maxn=8e6+5;
struct Node {
	int left,right;
	char v;
};
int Lpos,Rpos,S,T;
bool Rev=true;
struct List {
	Node a[maxn];
	int cnt;
	#define L(x) a[x].left
	#define R(x) a[x].right
	int newnode(char x) {
		a[++cnt]=(Node) {0,0,x};
		return cnt;
	}
	void push_down(int index) {
		int Left=L(index),Right=R(index);
		if(R(Left)!=index)swap(L(Left),R(Left));
		if(L(Right)!=index)swap(L(Right),R(Right));
	}
	void link(int x,int y) {
		if(x==Rpos&&y==Lpos)Rev=false;
		if(x==Lpos&&y==Rpos)Rev=true;
		R(x)=y;
		L(y)=x;
	}
	void cut(int x,int y) {
		R(x)=L(y)=0;
	}
	bool move_left(int index) {
		int Left=L(index),Right=R(index);
		push_down(Left);
		int LLeft=L(Left);
		if(Left==S)return false;
		cut(LLeft,Left),cut(Left,index),cut(index,Right);
		link(LLeft,index),link(index,Left),link(Left,Right);
		return true;
	}
	bool move_right(int index) {
		int Left=L(index),Right=R(index);
		push_down(Right);
		int RRight=R(Right);
		if(Right==T)return false;
		cut(Left,index),cut(index,Right),cut(Right,RRight);
		link(Left,Right),link(Right,index),link(index,RRight);
		return true;
	}
	void insert(int index,int New) {
		int Left=L(index);
		cut(Left,index);
		link(Left,New),link(New,index);
	}
	bool del(int index) {
		int Right=R(index),RRight=R(Right);
		push_down(Right);
		if(Right==T)return false;
		cut(index,Right),cut(Right,RRight);
		link(index,RRight);
		return true;
	}
	void reverse() {
		int Left=R(Lpos),Right=L(Rpos);
		cut(Lpos,Left),cut(Right,Rpos);
		swap(L(Left),R(Left));
		swap(L(Right),R(Right));
		link(Lpos,Right),link(Left,Rpos);
	}
	void show() {
		int index=Lpos;
		while(L(index)!=S) {
			push_down(index);
			index=L(index);
		}
		while(index!=T) {
			push_down(index);
			if(index!=Lpos&&index!=Rpos)putchar(a[index].v);
			index=R(index);
		}
		putchar('\n');
	}
} list;
char s[maxn];
int t;
int main() {
	S=list.newnode('\0'),T=list.newnode('\0');
	Lpos=list.newnode('['),Rpos=list.newnode(']');
	list.link(S,Lpos),list.link(Rpos,T);
	scanf("%s",s);
	int len=strlen(s),last=Lpos;
	for(int i=1; i<=len; i++) {
		int now=list.newnode(s[i-1]);
		list.link(last,now);
		last=now;
	}
	list.link(last,Rpos);
	t=Get_Int();
	while(t--) {
		char opt=' ';
		while(opt!='<'&&opt!='>'&&opt!='I'&&opt!='D'&&opt!='R'&&opt!='S')opt=getchar();
		if(opt=='<') {
			char w=' ';
			while(w!='L'&&w!='R')w=getchar();
			bool bj;
			if(w=='L')bj=list.move_left(Lpos);
			else bj=list.move_left(Rpos);
			if(bj)puts("T");
			else puts("F");
		} else if(opt=='>') {
			char w=' ';
			while(w!='L'&&w!='R')w=getchar();
			bool bj;
			if(w=='L')bj=list.move_right(Lpos);
			else bj=list.move_right(Rpos);
			if(bj)puts("T");
			else puts("F");
		} else if(opt=='I') {
			puts("T");
			char w=' ',v=' ';
			while(w!='L'&&w!='R')w=getchar();
			while(v<33||v>126)v=getchar();
			int New=list.newnode(v);
			if(w=='L')list.insert(Lpos,New);
			else list.insert(Rpos,New);
		} else if(opt=='D') {
			char w=' ',v=' ';
			while(w!='L'&&w!='R')w=getchar();
			bool bj;
			if(w=='L')bj=list.del(Lpos);
			else bj=list.del(Rpos);
			if(bj)puts("T");
			else puts("F");
		} else if(opt=='R') {
			if(!Rev||list.R(Lpos)==Rpos)puts("F");
			else {
				puts("T");
				list.reverse();
			}
		} else if(opt=='S')list.show();
	}
	return 0;
}

相关文章
姥爷们赏瓶冰阔落吧~