1. 首页
  2. Let's OI!
  3. 正文

bzoj1012: [JSOI2008]最大数maxnumber【线段树/单调队列】

  • 内容
  • 评论
  • 相关

算是挺简单的题目

题目点击这里

看上去很像数据结构题目（虽然的确是），由于操作数不超过20W，所以最终数列中的元素数量都不会超过20W，所以可以开一个20W长的线段树，一开始全是0，这样插入就只要依次插入就可以，查询就要记录当前数列中的元素数量，查询区间最大值就行，这样时间复杂度是O(NlogN)，可以解决这个问题。

PS：网上有人说可以用单调队列+二分，没仔细研究。。。

代码：

var
  t:array[1..524288]of longint;
  n,m,i,j,k,p,ans,d:longint;
  c:char;
function max(a,b:longint):longint;
begin
  if a>b then exit(a) else exit(b);
end;
procedure add(l,r,x:longint);
var
  m:longint;
begin
  if l=r then
  begin
    t[x]:=(ans+k) mod d;
    exit;
  end;
  m:=(l+r) shr 1;
  if m>=p then add(l,m,x shl 1)
  else add(m+1,r,x shl 1 or 1);
  t[x]:=max(t[x shl 1],t[x shl 1 or 1]);
end;
function ask(l,r,x:longint):longint;
var
  m,ans:longint;
begin
  if (l>=p-k) and (r<=p-1) then exit(t[x]);
  m:=(l+r) shr 1;
  ans:=0;
  if m>=p-k then ans:=max(ans,ask(l,m,x shl 1));
  if m+1<=p-1 then ans:=max(ans,ask(m+1,r,x shl 1 or 1));
  exit(ans);
end;
begin
  readln(m,d);
  n:=200000;
  ans:=0;
  p:=1;
  for i:=1 to m do
  begin
    read(c);
    if c='A' then
    begin
      readln(c,k);
      add(1,n,1);
      inc(p);
    end;
    if c='Q' then
    begin
      readln(c,k);
      ans:=ask(1,n,1);
      writeln(ans);
    end;
  end;
end.

评论

0条评论

发表回复

您的电子邮箱地址不会被公开。 必填项已用*标注

此站点使用Akismet来减少垃圾评论。了解我们如何处理您的评论数据。