学步园

以前对线段树的理解真是太肤浅了，看了zkw大牛的ppt发现线段树真是优美。。。

求最后几个数的最大值代码（看起来像树状数组，但没lowbit）。const inf='maxnumber.in';<br /> ouf='maxnumber.out';<br /> var a:array[1..5000000]of longint;<br /> n,m,p,m1,s:longint;<br /> ans:int64;<br /> procedure init;<br /> var i,l,r,j:longint;<br /> y:int64;<br /> x:char;<br /> begin<br /> assign(input,inf);reset(input);<br /> assign(output,ouf);rewrite(output);<br /> readln(m,p);<br /> fillchar(a,sizeof(a),0);<br /> m1:=1;<br /> while m1<m do m1:=m1*2;<br /> m1:=m1*2-1;<br /> ans:=0;s:=0;<br /> for j:=1 to m do begin<br /> readln(x,y);<br /> if x='A' then begin<br /> y:=(ans+y)mod p;<br /> inc(s);a[s+m1]:=y;<br /> i:=(s+m1)>>1;<br /> while i<>0 do begin<br /> if y>a[i] then a[i]:=y;<br /> i:=i>>1<br /> end<br /> end<br /> else if x='Q' then begin<br /> ans:=-maxlongint;<br /> l:=s-y;r:=s+1;<br /> l:=l+m1;r:=r+m1;<br /> while not(l xor r=1) do begin<br /> if l and 1=0 then if a[l+1]>ans then ans:=a[l+1];<br /> if r and 1=1 then if a[r-1]>ans then ans:=a[r-1];<br /> l:=l>>1;r:=r>>1<br /> end;<br /> writeln(ans)<br /> end<br /> end;<br /> close(input);<br /> close(output)<br /> end;<br /> begin<br /> init;<br /> end.