bzoj1012: [JSOI2008]最大数maxnumber【线段树/单调队列】
算是挺简单的题目
看上去很像数据结构题目(虽然的确是),由于操作数不超过20W,所以最终数列中的元素数量都不会超过20W,所以可以开一个20W长的线段树,一开始全是0,这样插入就只要依次插入就可以,查询就要记录当前数列中的元素数量,查询区间最大值就行,这样时间复杂度是O(NlogN),可以解决这个问题。
PS:网上有人说可以用单调队列+二分,没仔细研究。。。
代码:
var t:array[1..524288]of longint; n,m,i,j,k,p,ans,d:longint; c:char; function max(a,b:longint):longint; begin if a>b then exit(a) else exit(b); end; procedure add(l,r,x:longint); var m:longint; begin if l=r then begin t[x]:=(ans+k) mod d; exit; end; m:=(l+r) shr 1; if m>=p then add(l,m,x shl 1) else add(m+1,r,x shl 1 or 1); t[x]:=max(t[x shl 1],t[x shl 1 or 1]); end; function ask(l,r,x:longint):longint; var m,ans:longint; begin if (l>=p-k) and (r<=p-1) then exit(t[x]); m:=(l+r) shr 1; ans:=0; if m>=p-k then ans:=max(ans,ask(l,m,x shl 1)); if m+1<=p-1 then ans:=max(ans,ask(m+1,r,x shl 1 or 1)); exit(ans); end; begin readln(m,d); n:=200000; ans:=0; p:=1; for i:=1 to m do begin read(c); if c='A' then begin readln(c,k); add(1,n,1); inc(p); end; if c='Q' then begin readln(c,k); ans:=ask(1,n,1); writeln(ans); end; end; end.
发表回复