学步园

      哎呀，不早了，这道题从9点调到了11：30，总之这道题和之前的【poj3580】非常相似，很欣慰的是这次编写的时候思维非常连贯，一口气写完，debug了2个小时发现一直是读入萎了~~，不知道我的数据是不是noi官网的，总之有些点和题目描述的不一样，比如说GET-MAX操作后面诡异的给我来了几个空格，我就一直在201和215之间徘徊。

      依然是裸的splay，发现这次的时间有一些惊险，某个点我要8S才跑得出来，主要是回收废节点编号慢了，去掉就大约是3S左右，（ms时限有10S），开了release以后神速！每个点都不超过2S，很奇怪啊。

      这道题貌似是没有内存限制的，但是为了不把自己机器卡爆，加了一个回收站把不要的节点编号回收回来下次继续使用。

代码仅供自己观摩。。。。（WS缩行流）

program ex2; const maxn=500005;<br /> var<br /> max,w,s,sum,lm,rm,c,l,r,next:array[0..maxn] of longint;<br /> fan:array[0..maxn] of boolean;<br /> i,j,k,n,m,pos,tot,tmp,root,head,ask:longint;<br /> task:string;p:char;</p> <p>procedure getmax(var a:longint;b:longint);begin if a<b then a:=b end;</p> <p>procedure update(i:longint);var ll,rr:longint;<br /> begin<br /> ll:=l[i];rr:=r[i];<br /> s[i]:=s[ll]+s[rr]+1;<br /> sum[i]:=sum[ll]+sum[rr]+w[i];<br /> lm[i]:=lm[ll];rm[i]:=rm[rr];<br /> getmax(lm[i],lm[rr]+sum[ll]+w[i]);<br /> getmax(rm[i],rm[ll]+sum[rr]+w[i]);<br /> max[i]:=lm[rr]+rm[ll]+w[i];<br /> getmax(max[i],max[ll]);<br /> getmax(max[i],max[rr]);<br /> end;</p> <p>procedure left(var i:longint);var j:longint;<br /> begin<br /> j:=r[i];r[i]:=l[j];l[j]:=i;<br /> update(i);update(j);i:=j;<br /> end;</p> <p>procedure right(var i:longint);var j:longint;<br /> begin<br /> j:=l[i];l[i]:=r[j];r[j]:=i;<br /> update(i);update(j);i:=j;<br /> end;</p> <p>procedure put(i,cc:longint;ff:boolean);<br /> begin<br /> if i=0 then exit;<br /> if ff then begin<br /> tmp:=l[i];l[i]:=r[i];r[i]:=tmp;<br /> tmp:=lm[i];lm[i]:=rm[i];rm[i]:=tmp;<br /> fan[i]:=not fan[i];<br /> end;<br /> if cc<1001 then begin<br /> c[i]:=cc;w[i]:=cc;sum[i]:=s[i]*cc;<br /> max[i]:=0;getmax(max[i],sum[i]);<br /> lm[i]:=max[i];rm[i]:=max[i];<br /> if max[i]=0 then max[i]:=cc;<br /> end;<br /> end;</p> <p>procedure splay(var i:longint;k:longint);<br /> begin<br /> put(l[i],c[i],fan[i]);put(r[i],c[i],fan[i]);<br /> fan[i]:=false;c[i]:=10000;tmp:=s[l[i]]+1;<br /> if k=tmp then exit else<br /> if k>tmp then begin<br /> splay(r[i],k-tmp);left(i);<br /> end else begin<br /> splay(l[i],k);right(i);<br /> end;<br /> end;</p> <p>procedure buildtree(ll,rr:longint;var i:longint);<br /> begin<br /> if ll>rr then exit;<br /> i:=(ll+rr)div 2;<br /> buildtree(ll,i-1,l[i]);<br /> buildtree(i+1,rr,r[i]);<br /> update(i);<br /> end;</p> <p>procedure release(i:longint);<br /> begin<br /> if i=0 then exit;<br /> next[i]:=head;head:=i;<br /> release(l[i]);release(r[i]);<br /> end;</p> <p>begin<br /> assign(input,'sequence.in');reset(input);<br /> assign(output,'sequence.out');rewrite(output);<br /> readln(n,m);<br /> fillchar(c,sizeof(c),1);<br /> w[1]:=-10000;w[n+2]:=-10000;max[0]:=-10000;<br /> for i:=2 to n+1 do read(w[i]);readln;<br /> for i:=n+3 to maxn do begin<br /> next[i]:=head;head:=i;<br /> end;<br /> buildtree(1,n+2,root);<br /> for m:=1 to m do begin<br /> task:='';read(p);<br /> while not (p in ['A'..'Z','-']) do read(p);<br /> while p in ['A'..'Z','-'] do begin<br /> task:=task+p;read(p);<br /> end;<br /> if task='INSERT' then begin<br /> read(pos,tot);splay(root,pos+2);<br /> for tot:=1 to tot do begin<br /> read(j);<br /> k:=head;head:=next[head];<br /> w[k]:=j;l[k]:=l[root];l[root]:=k;<br /> r[k]:=0;c[k]:=10000;fan[k]:=false;<br /> update(k);update(root);<br /> end;<br /> end else<br /> if task='DELETE' then begin<br /> read(pos,tot);<br /> splay(root,pos);splay(root,pos+tot+1);<br /> release(r[l[root]]);r[l[root]]:=0;<br /> update(l[root]);update(root);<br /> end else<br /> if task='MAKE-SAME' then begin<br /> read(pos,tot,j);<br /> splay(root,pos);splay(root,pos+tot+1);<br /> put(r[l[root]],j,false);<br /> update(l[root]);update(root);<br /> end else<br /> if task='REVERSE' then begin<br /> read(pos,tot);<br /> splay(root,pos);splay(root,pos+tot+1);<br /> put(r[l[root]],10000,true);<br /> update(l[root]);update(root);<br /> end else<br /> if task='GET-SUM' then begin<br /> read(pos,tot);<br /> splay(root,pos);splay(root,pos+tot+1);<br /> writeln(sum[r[l[root]]]);<br /> end else writeln(max[root]);<br /> end;<br /> close(input);close(output);<br /> end.