显然，如果使用倍增，用num[i,j]表示从i-2^j+1到i的所有数的最大值，则后面插入的数对前面插入的数是没有影响的。这样就可以使用倍增，插入和查找都是logn的复杂度，妥妥的。
program p1012; var num:array[1..200000,0..17] of int64; i,j:longint; m,d,k1,len,k2,now:int64; ch:char; function max(k1,k2:longint):longint; begin if k1<k2 then exit(k2) else exit(k1); end; begin readln(m,d); k1:=0; fillchar(num,sizeof(num),$3f); for i:=1 to m do begin read(ch); if ch='A' then begin inc(len); readln(k2); k2:=(k2+k1) mod d; num[len,0]:=k2; for j:=1 to 17 do if 1 shl j<=len then num[len,j]:=max(num[len-1 shl (j-1),j-1],num[len,j-1]) else break; end else begin readln(k2); k1:=0; now:=len; for j:=17 downto 0 do if k2 and (1 shl j)>0 then begin k1:=max(k1,num[now,j]); now:=now-(1 shl j); end; writeln(k1); end; end; end.
评论 (0)
