10
21
2013
0

【BZOJ1012】【JSOI2008】最大数maxnumber【倍增】

显然,如果使用倍增,用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.
Category: 倍增 | Tags: | Read Count: 902

登录 *


loading captcha image...
(输入验证码)
or Ctrl+Enter

Host by is-Programmer.com | Power by Chito 1.3.3 beta | Theme: Aeros 2.0 by TheBuckmaker.com