首页 > 代码库 > JSOI2008最大数(线段树)
JSOI2008最大数(线段树)
注意到数列只增不减,而题目中又明确说道m<=200000;这样的数据规模线段树完全可以承受得了。所以我们可以事先建好一棵200000个子节点的线段树,然后求极值就好了。
type node=record l,r,mx:longint;end; var i,j,m,p,x,tmp,tot:longint; ch:char; t:array[0..1500000] of node; function max(x,y:longint):longint; begin if x>y then exit(x) else exit(y); end; procedure build(x,y,k:longint); var mid:longint; begin with t[k] do begin l:=x;r:=y; if l=r then exit; mid:=(l+r)>>1; build(x,mid,k<<1); build(mid+1,r,k<<1+1); end; end; procedure change(x,y,k:longint); var mid:longint; begin with t[k] do begin if l=r then begin mx:=y; exit; end; mid:=(l+r)>>1; if x>mid then change(x,y,k<<1+1) else change(x,y,k<<1); mx:=max(t[k<<1].mx,t[k<<1+1].mx); end; end; function getmx(x,y,k:longint):longint; var mid:longint; begin with t[k] do begin if (l=x) and (r=y) then exit(mx); mid:=(l+r)>>1; if x>mid then exit(getmx(x,y,k<<1+1)) else if y<=mid then exit(getmx(x,y,k<<1)) else exit(max(getmx(x,mid,k<<1),getmx(mid+1,y,k<<1+1))); end; end; procedure main; begin build(1,200000,1); readln(m,p);tmp:=0;tot:=0; for i:=1 to m do begin read(ch); if ch=‘A‘ then begin readln(x); inc(tot); change(tot,(x+tmp) mod p,1); end else begin readln(x); tmp:=getmx(tot-x+1,tot,1); writeln(tmp); end; end; end; begin main; end.
不过话说起来,1A的感觉真棒!
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。