首页 > 代码库 > JSOI最大值 (线段树)
JSOI最大值 (线段树)
change 单点修改
query 区间最值
1 Program XJOI2321; 2 const maxn=200008; 3 var l,r,max:array[0..maxn*4] of longint; 4 i,m,n,ans,p,x:longint; 5 ch:char; 6 function mx(a,b:longint):longint; 7 begin 8 if a>b then exit(a) else exit(b); 9 end;10 procedure up(x:longint);11 begin12 max[x]:=mx(max[x*2],max[x*2+1]);13 end;14 procedure build(x,lt,rt:longint);15 var mid:longint;16 begin17 l[x]:=lt;18 r[x]:=rt;19 if lt=rt then20 begin21 max[i]:=0;22 exit;23 end;24 mid:=(lt+rt) div 2;25 build(x*2,lt,mid);26 build(x*2+1,mid+1,rt);27 up(x);28 end;29 procedure change(x,G,val:longint);30 var mid:longint;31 begin32 if l[x]=r[x] then33 begin34 max[x]:=val;35 exit;36 end;37 mid:=(l[x]+r[x]) div 2;38 if G<=mid then change(x*2,G,val) else change(x*2+1,G,val);39 up(x);40 end;41 function query(x,lt,rt:longint):longint;42 var mid,as:longint;43 begin44 if (lt<=l[x]) and (r[x]<=rt) then exit(max[x]);45 mid:=(l[x]+r[x]) div 2;46 as:=0;47 if lt<=mid then as:=mx(as,query(x*2,lt,rt));48 if mid<rt then as:=mx(as,query(x*2+1,lt,rt));49 exit(as);50 end;51 begin52 readln(m,p);53 ans:=0; n:=0;54 build(1,1,m);55 for i:=1 to m do56 begin57 readln(ch,x);58 if ch=‘A‘ then59 begin60 x:=(x+ans) mod p;61 inc(n);62 change(1,n,x);63 end else64 begin65 ans:=query(1,n-x+1,n);66 writeln(ans);67 end;68 69 end;70 71 end.
JSOI最大值 (线段树)
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。