注意到数列只增不减,而题目中又明确说道m<=200000;这样的数据规模线段树完全可以承受得了。所以我们可以事先建好一棵200000个子节点的线段树,然后求极值就好了。
type node=record l,r,mx:longint;end;
var i,j,m,p,x,tmp,tot:longint;
ch:char;
t:array[..] 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)>>;
build(x,mid,k<<);
build(mid+,r,k<<+);
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)>>;
if x>mid then change(x,y,k<<+)
else change(x,y,k<<);
mx:=max(t[k<<].mx,t[k<<+].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)>>;
if x>mid then exit(getmx(x,y,k<<+))
else if y<=mid then exit(getmx(x,y,k<<))
else exit(max(getmx(x,mid,k<<),getmx(mid+,y,k<<+)));
end;
end;
procedure main;
begin
build(,,);
readln(m,p);tmp:=;tot:=;
for i:= to m do
begin
read(ch);
if ch='A' then
begin
readln(x);
inc(tot);
change(tot,(x+tmp) mod p,);
end
else
begin
readln(x);
tmp:=getmx(tot-x+,tot,);
writeln(tmp);
end;
end;
end;
begin
main;
end.
不过话说起来,1A的感觉真棒!
(update:ms还可以用单调栈,不过没实现过)