1507: [NOI2003]Editor
Time Limit: 5 Sec Memory Limit: 162 MB
Submit: 1908 Solved: 738
[Submit][Status]
Description
Input
输入文件editor.in的第一行是指令条数t，以下是需要执行的t个操作。其中： 为了使输入文件便于阅读，Insert操作的字符串中可能会插入一些回车符，请忽略掉它们（如果难以理解这句话，可以参考样例）。 除了回车符之外，输入文件的所有字符的ASCII码都在闭区间[32, 126]内。且行尾没有空格。 这里我们有如下假定： MOVE操作不超过50000个，INSERT和DELETE操作的总个数不超过4000，PREV和NEXT操作的总个数不超过200000。 所有INSERT插入的字符数之和不超过2M（1M=1024*1024），正确的输出文件长度不超过3M字节。 DELETE操作和GET操作执行时光标后必然有足够的字符。MOVE、PREV、NEXT操作必然不会试图把光标移动到非法位置。 输入文件没有错误。 对C++选手的提示：经测试，最大的测试数据使用fstream进行输入有可能会比使用stdio慢约1秒。
Output
输出文件editor.out的每行依次对应输入文件中每条GET指令的输出。
Sample Input
15
Insert 26
abcdefghijklmnop
qrstuv wxy
Move 16
Delete 11
Move 5
Insert 1
^
Next
Insert 1
_
Next
Next
Insert 4
.\/.
Get 4
Prev
Insert 1
^
Move 0
Get 22
Insert 26
abcdefghijklmnop
qrstuv wxy
Move 16
Delete 11
Move 5
Insert 1
^
Next
Insert 1
_
Next
Next
Insert 4
.\/.
Get 4
Prev
Insert 1
^
Move 0
Get 22
Sample Output
.\/.
abcde^_^f.\/.ghijklmno
abcde^_^f.\/.ghijklmno
HINT
Source
题解：
我靠。。。
刚开始WA,后来栈溢出，然后TLE，还让不让人活了。。。
代码：
1.递归，中序遍历输出结果
{$inline on}
{$M 10000000,0,maxlongint}
const maxn=+;
var s,fa:array[..maxn] of longint;
v:array[..maxn] of char;
c:array[..maxn,..] of longint;
i,j,n,m,x,y,z,tot,rt,now,l,r:longint;
ch:char;
st,st2:ansistring;
procedure pushup(x:longint);inline;
begin
s[x]:=s[c[x,]]+s[c[x,]]+;
end;
procedure rotate(x:longint;var k:longint);inline;
var y,z,l,r:longint;
begin
y:=fa[x];z:=fa[y];
l:=ord(c[y,]=x);r:=l xor ;
if y=k then k:=x else c[z,ord(c[z,]=y)]:=x;
fa[x]:=z;fa[y]:=x;fa[c[x,r]]:=y;
c[y,l]:=c[x,r];c[x,r]:=y;
pushup(y);pushup(x);
end;
procedure splay(x:longint;var k:longint);inline;
var y,z:longint;
begin
while x<>k do
begin
y:=fa[x];z:=fa[y];
if y<>k then
if (c[z,]=y) xor (c[y,]=x) then rotate(x,k)
else rotate(y,k);
rotate(x,k);
end;
end;
function find(x,rank:longint):longint;inline;
var l,r:longint;
begin
l:=c[x,];r:=c[x,];
if s[l]+=rank then exit(x)
else if s[l]>=rank then exit(find(l,rank))
else exit(find(r,rank-s[l]-));
end;
procedure print(x:longint);inline;
begin
if x= then exit;
print(c[x,]);
write(v[x]);
print(c[x,]);
end;
procedure main;
begin
readln(n);
l:=maxn-+;r:=maxn-+;
rt:=l;
c[l,]:=r;fa[r]:=l;s[l]:=;s[r]:=;
now:=;tot:=;
for i:= to n do
begin
read(ch);
case ch of
'P':begin
readln;
dec(now);
end;
'N':begin
readln;
inc(now);
end;
'M':begin
while ch<>' ' do read(ch);readln(x);
now:=x+;
end;
'I':begin
while ch<>' ' do read(ch);readln(m);
readln(st);while length(st)<m do begin readln(st2);st:=st+st2;end;
for j:= to m do begin inc(tot);fa[tot]:=tot-;v[tot]:=st[j];s[tot]:=m-j+;c[tot,]:=;if j<>m then c[tot,]:=tot+ else c[tot,]:=;end;
x:=find(rt,now);y:=find(rt,now+);
splay(x,rt);splay(y,c[x,]);
c[y,]:=tot-m+;fa[tot-m+]:=y;
pushup(y);pushup(x);
end;
'D':begin
while ch<>' ' do read(ch);readln(m);
x:=find(rt,now);y:=find(rt,now+m+);
splay(x,rt);splay(y,c[x,]);
z:=c[y,];fa[z]:=;c[y,]:=;
pushup(y);pushup(x);
end;
'G':begin
while ch<>' ' do read(ch);readln(m);
x:=find(rt,now);y:=find(rt,now+m+);
splay(x,rt);splay(y,c[x,]);
print(c[y,]);writeln;
end;
end;
end;
end;
begin
assign(input,'input.txt');assign(output,'output.txt');
reset(input);rewrite(output);
main;
close(input);close(output);
end.
2.人工栈
{$inline on}
{$M 1000000000,0,maxlongint}
const maxn=+;
var s,fa:array[..maxn] of longint;
v:array[..maxn] of char;
c:array[..maxn,..] of longint;
i,j,n,m,x,y,z,tot,rt,now,l,r,top:longint;
ch:char;
sta:array[..maxn*] of record a,b:longint;end;
st,st2:ansistring;
function min(x,y:longint):longint;inline;
begin
if x<y then exit(x) else exit(y);
end;
procedure pushup(x:longint);inline;
begin
s[x]:=s[c[x,]]+s[c[x,]]+;
end;
procedure rotate(x:longint;var k:longint);inline;
var y,z,l,r:longint;
begin
y:=fa[x];z:=fa[y];
l:=ord(c[y,]=x);r:=l xor ;
if y=k then k:=x else c[z,ord(c[z,]=y)]:=x;
fa[x]:=z;fa[y]:=x;fa[c[x,r]]:=y;
c[y,l]:=c[x,r];c[x,r]:=y;
pushup(y);pushup(x);
end;
procedure splay(x:longint;var k:longint);inline;
var y,z:longint;
begin
while x<>k do
begin
y:=fa[x];z:=fa[y];
if y<>k then
if (c[z,]=y) xor (c[y,]=x) then rotate(x,k)
else rotate(y,k);
rotate(x,k);
end;
end;
procedure print(x:longint);
var i,j:longint;
begin
top:=;sta[top].a:=x;sta[top].b:=;
while top> do
begin
i:=sta[top].a;j:=sta[top].b;dec(top);
if j= then write(v[i])
else
begin
if c[i,]> then
begin
inc(top);sta[top].a:=c[i,];sta[top].b:=;
end;
inc(top);sta[top].a:=i;sta[top].b:=;
if c[i,]> then
begin
inc(top);sta[top].a:=c[i,];sta[top].b:=;
end;
end;
end;
end;
function find(x,rank:longint):longint;inline;
var l,r:longint;
begin
l:=c[x,];r:=c[x,];
if s[l]+=rank then exit(x)
else if s[l]>=rank then exit(find(l,rank))
else exit(find(r,rank-s[l]-));
end;
procedure main;
begin
readln(n);
l:=maxn-+;r:=maxn-+;
rt:=l;
c[l,]:=r;fa[r]:=l;s[l]:=;s[r]:=;
now:=;tot:=;
for i:= to n do
begin
read(ch);
case ch of
'P':begin
readln;
dec(now);
end;
'N':begin
readln;
inc(now);
end;
'M':begin
while ch<>' ' do read(ch);readln(x);
now:=x+;
end;
'I':begin
while ch<>' ' do read(ch);readln(m);
readln(st);while length(st)<m do begin readln(st2);st:=st+st2;end;
for j:= to m do begin inc(tot);fa[tot]:=tot-;v[tot]:=st[j];s[tot]:=m-j+;c[tot,]:=;if j<>m then c[tot,]:=tot+ else c[tot,]:=;end;
x:=find(rt,now);y:=find(rt,now+);
splay(x,rt);splay(y,c[x,]);
c[y,]:=tot-m+;fa[tot-m+]:=y;
pushup(y);pushup(x);
end;
'D':begin
while ch<>' ' do read(ch);readln(m);
x:=find(rt,now);y:=find(rt,min(tot+,now+m+));
splay(x,rt);splay(y,c[x,]);
z:=c[y,];fa[z]:=;c[y,]:=;
pushup(y);pushup(x);
end;
'G':begin
while ch<>' ' do read(ch);readln(m);
x:=find(rt,now);y:=find(rt,min(tot+,now+m+));
splay(x,rt);splay(y,c[x,]);
print(c[y,]);writeln;
end;
end;
end;
end;
begin
assign(input,'input.txt');assign(output,'output.txt');
reset(input);rewrite(output);
main;
close(input);close(output);
end.