| 记录编号 |
53801 |
评测结果 |
AAAAAAAAAA |
| 题目名称 |
[HNOI 2011] 括号修复 |
最终得分 |
100 |
| 用户昵称 |
 DavidMason |
是否通过 |
通过 |
| 代码语言 |
Pascal |
运行时间 |
4.995 s |
| 提交时间 |
2013-03-06 08:23:42 |
内存使用 |
0.55 MiB |
显示代码纯文本
type link=^rec;
rec=record
l,r,f:link;
size,v,sum,maxl,maxr,minl,minr,pos,same,time,transtime:longint;
reverse,trans:boolean;
end;
var
n,m:longint;
root,null:link;
data:array[0..100000] of longint;
procedure init;
begin
assign(input,'brackets.in'); reset(input);
assign(output,'brackets.out'); rewrite(output);
end;
procedure terminate;
begin
close(input); close(output); halt;
end;
function max(a,b:longint):longint;
begin
if a>b then exit(a) else exit(b);
end;
function makelink(x:longint):link;
var
p:link;
begin
new(p); p^.l:=null; p^.r:=null; p^.f:=null; p^.size:=1; p^.v:=x;
p^.sum:=x; p^.maxl:=x; p^.maxr:=x; p^.minl:=x; p^.minr:=x;
p^.reverse:=false; p^.trans:=false; p^.transtime:=0; p^.time:=0; p^.same:=0; exit(p);
end;
procedure updata(p:link);
begin
p^.size:=p^.l^.size+p^.r^.size+1; p^.sum:=p^.l^.sum+p^.r^.sum+p^.v;
p^.maxl:=max(max(p^.l^.maxl,p^.l^.sum+p^.v+p^.r^.maxl),0);
p^.maxr:=max(max(p^.r^.maxr,p^.r^.sum+p^.v+p^.l^.maxr),0);
p^.minl:=max(max(p^.l^.minl,-p^.l^.sum-p^.v+p^.r^.minl),0);
p^.minr:=max(max(p^.r^.minr,-p^.r^.sum-p^.v+p^.l^.minr),0);
end;
function build(l,r:longint):link;
var
mid:longint; p:link;
begin
if l>r then exit(null); mid:=(l+r) shr 1; p:=makelink(data[mid]); p^.pos:=mid;
p^.l:=build(l,mid-1); if p^.l<>null then p^.l^.f:=p;
p^.r:=build(mid+1,r); if p^.r<>null then p^.r^.f:=p;
updata(p); exit(p);
end;
procedure makereverse(p:link);
var
t:longint; tt:link;
begin
if p=null then exit; p^.reverse:=not p^.reverse;
tt:=p^.l; p^.l:=p^.r; p^.r:=tt;
t:=p^.maxl; p^.maxl:=p^.maxr; p^.maxr:=t;
t:=p^.minl; p^.minl:=p^.minr; p^.minr:=t;
end;
procedure makesame(p:link; x,time:longint);
begin
if p=null then exit; p^.time:=time; p^.same:=x;
p^.v:=x; p^.sum:=p^.size*x;
if x>=0 then begin p^.maxl:=p^.size*x; p^.maxr:=p^.size*x; p^.minl:=0; p^.minr:=0 end else
begin p^.maxl:=0; p^.maxr:=0; p^.minl:=-p^.size*x; p^.minr:=-p^.size*x; end;
end;
procedure maketrans(p:link; time:longint);
var
t:longint;
begin
if p=null then exit;
if (p^.time>0) and (p^.time<time) then begin
p^.trans:=false; makesame(p,-p^.same,time); exit;
end;
p^.transtime:=time; p^.trans:=not p^.trans;
p^.sum:=-p^.sum; p^.v:=-p^.v;
t:=p^.maxl; p^.maxl:=p^.minl; p^.minl:=t;
t:=p^.maxr; p^.maxr:=p^.minr; p^.minr:=t;
end;
procedure down(p:link);
begin
if p^.reverse then begin makereverse(p^.l); makereverse(p^.r); p^.reverse:=false; end;
if p^.trans then begin maketrans(p^.l,p^.transtime); maketrans(p^.r,p^.transtime); p^.trans:=false; p^.transtime:=0; end;
if p^.same<>0 then begin makesame(p^.l,p^.same,p^.time); makesame(p^.r,p^.same,p^.time); p^.same:=0; p^.time:=0; end;
end;
procedure rotate(p:link; w:longint);
var
q:link;
begin
q:=p^.f; down(q); down(p);
if w=1 then begin
q^.r:=p^.l;
if p^.l<>null then p^.l^.f:=q;
end else begin
q^.l:=p^.r;
if p^.r<>null then p^.r^.f:=q;
end;
p^.f:=q^.f;
if q^.f<>null then
if q=q^.f^.l then q^.f^.l:=p else q^.f^.r:=p;
if w=1 then p^.l:=q else p^.r:=q; q^.f:=p;
if root=q then root:=p; updata(q);
end;
procedure splay(p,std:link);
var
q,r:link;
begin
down(p);
while p^.f<>std do begin
q:=p^.f; r:=q^.f;
if r=std then
if p=q^.l then rotate(p,2) else rotate(p,1)
else
if q=r^.l then
if p=q^.l then begin
rotate(q,2); rotate(p,2);
end else begin
rotate(p,1); rotate(p,2);
end
else
if p=q^.r then begin
rotate(q,1); rotate(p,1);
end else begin
rotate(p,2); rotate(p,1);
end;
end;
updata(p);
end;
procedure select(now:longint; std:link);
var
p:link; count:longint;
begin
p:=root;
while true do begin
down(p); count:=p^.l^.size;
if now=count+1 then break;
if now<=count then p:=p^.l else begin p:=p^.r; now:=now-count-1; end;
end;
splay(p,std);
end;
procedure insert(x,y:longint);
var
p:link; i:longint; ch:char;
begin
select(x,null); select(x+1,root);
for i:=1 to y do begin read(ch); if ch='(' then data[i]:=1 else data[i]:=-1; end;
p:=build(1,y); root^.r^.l:=p; p^.f:=root^.r;
splay(root^.r,null);
end;
procedure delete(p:link);
begin
if p=null then exit; delete(p^.l); if p^.v=1 then write('( ') else write(') ');
writeln(p^.pos); delete(p^.r);
end;
procedure main;
var
i:longint; ch:char; x,y,z:longint;
begin
readln(n,m);
null:=makelink(0); null^.size:=0; null^.sum:=0;
root:=makelink(0); root^.r:=makelink(0); root^.pos:=0;
root^.r^.f:=root; root^.r^.pos:=n+1; updata(root);
insert(1,n); readln;
for i:=1 to m do begin
read(ch);
if ch='R' then begin
read(ch,ch,ch,ch,ch,ch,ch); read(x,y);
read(ch,ch); readln; if ch='(' then z:=1 else z:=-1;
select(x,null); select(y+2,root);
makesame(root^.r^.l,z,i); splay(root^.r^.l,null);
end else
if ch='S' then begin
read(ch,ch,ch,ch); readln(x,y);
select(x,null); select(y+2,root);
makereverse(root^.r^.l); splay(root^.r^.l,null);
end else
if ch='I' then begin
read(ch,ch,ch,ch,ch,ch); readln(x,y); select(x,null); select(y+2,root);
maketrans(root^.r^.l,i); splay(root^.r^.l,null);
end else
if ch='Q' then begin
read(ch,ch,ch,ch,ch); readln(x,y); select(x,null); select(y+2,root);
writeln((root^.r^.l^.minl+1) div 2+(root^.r^.l^.maxr+1) div 2);
end;
end;
//writeln; delete(root);
end;
begin
init;
main;
terminate;
end.