首页 > 代码库 > 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最大值 (线段树)