JSOI2008最大数（线段树）

浏览数：14 / 时间：2015年06月09日

注意到数列只增不减，而题目中又明确说道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.