dwjshift's Blog

几道分块题

| Comments

原文发表时间:2014-04-24
update:本文讲的都是无修改的按序列分块做法
最近才开始玩乱搞神器分块……真是该打脸
先讲讲我目前所知的几种分块的姿势。假设分为块,每块大小为是某个块的开头,是某个块的结尾,首先你要知道每个查询
1、分块后预处理第块到第块的答案。查询时可能影响答案的只有中的元素,所以把,中的元素扫一遍更新答案。需要用一个辅助的数据结构存储区间中每个元素的信息。
2、分块后预处理第块到第块中每个元素的信息,扫一遍中的元素,并把这些元素的信息都添加到一个辅助数组中(或者直接添加到存第到第块信息的数组),边扫边更新答案,最后再把这些元素的信息从辅助数组中删掉(直接清空的话太慢)。
3、类似1,不过是预处理第块开头到后面每个位置的答案,查询时就可以直接得出的信息。
4、离线搞莫队算法(可以说是对询问分块?)。
update:其实上面的这个讲得不是很好……直接把上面所说的每个块的开头作为关键点,处理关键点之间的信息会更方便。下面的代码也都写的比较难看,勉强凑合着看看题解吧……

bzoj2724 蒲公英

记得先离散化。这题前三种分块都可做。第一种或第三种的话需要求区间某个元素出现次数,可以用数组存下每个数的出现位置然后二分来做。实际上还有另一种神姿势求区间出现次数,可以把前个元素都弄一个数组记录1-i中每个元素的出现次数,然后对这个数组进行分块,那就是在的基础上修改一个块就好了(可以说是可持久化的块状数组吧),这样查询区间出现次数就是的。我写的是第二种,复杂度是,虽然出题人的题解说,不过我这个热衷于用空间换时间的逗比把取到了57,是702,压着500+M过的。

code

{$inline on}
const
  size=702;
  qt=57;
var
  n,m,i,j,k,tot,last,t,ans,first,l,r:longint;
  a,b,temp,num:array[0..40000]of longint;
  s:array[1..qt,1..qt+1,0..40000]of longint;
    
procedure swap(var x,y:longint);inline;
begin
  t:=x;
  x:=y;
  y:=t;
end;
    
procedure qsort(l,r:longint);
var
  i,j,x:longint;
begin
  i:=l;
  j:=r;
  x:=a[b[(l+r) shr 1]];
  repeat
    while a[b[i]]<x do
      inc(i);
    while a[b[j]]>x do
      dec(j);
    if i<=j then
      begin
        swap(b[i],b[j]);
        inc(i);
        dec(j);
      end;
  until i>j;
  if i<r then
    qsort(i,r);
  if l<j then
    qsort(l,j);
end;
    
procedure init;
begin
  read(n,m);
  for i:=1 to n do
    begin
      read(a[i]);
      b[i]:=i;
    end;
  qsort(1,n);
  for i:=1 to n do
    if a[b[i]]=last then
      a[b[i]]:=tot
    else
      begin
        last:=a[b[i]];
        inc(tot);
        a[b[i]]:=tot;
        num[tot]:=last;
      end;
  i:=1;
  repeat
    k:=i;
    s[i,i,0]:=1;
    for j:=(i-1)*size+1 to n do
      begin
        inc(s[i,k,a[j]]);
        if (s[i,k,a[j]]>s[i,k,s[i,k,0]])or(s[i,k,a[j]]=s[i,k,s[i,k,0]])and(a[j]<s[i,k,0]) then
          s[i,k,0]:=a[j];
        if j mod size=0 then
          begin
            inc(k);
            s[i,k]:=s[i,k-1];
          end;
      end;
    inc(i);
  until (i-1)*size+1>n;
end;
    
procedure insert(x:longint);inline;
begin
  inc(temp[x]);
  if (temp[x]+s[first,last,x]>temp[ans]+s[first,last,ans])
  or(temp[x]+s[first,last,x]=temp[ans]+s[first,last,ans])and(x<ans) then
    ans:=x;
end;
    
begin
  init;
  for m:=m downto 1 do
    begin
      read(l,r);
      l:=(l+num[ans]-1) mod n+1;
      r:=(r+num[ans]-1) mod n+1;
      if l>r then
        swap(l,r);
      for first:=qt+1 downto 2 do
        if l>(first-2)*size then
          break;
      for last:=0 to qt-1 do
        if r<(last+1)*size then
          break;
      if first>last then
        begin
          ans:=1;
          for i:=l to r do
            begin
              inc(temp[a[i]]);
              if (temp[a[i]]>temp[ans])or(temp[a[i]]=temp[ans])and(a[i]<ans) then
                ans:=a[i];
            end;
          for i:=l to r do
            dec(temp[a[i]]);
          writeln(num[ans]);
          continue;
        end;
      ans:=s[first,last,0];
      for i:=l to (first-1)*size do
        insert(a[i]);
      for i:=last*size+1 to r do
        insert(a[i]);
      writeln(num[ans]);
      for i:=l to (first-1)*size do
        dec(temp[a[i]]);
      for i:=last*size+1 to r do
        dec(temp[a[i]]);
    end;
end.

bzoj2821 作诗

要求在线……还是考虑前三种。后两种128M的空间的话的取值范围比较小,所以还是算了吧。所以我写了第一种,用的是数组中二分的方法查询区间出现次数。空间挺小的所以要加以利用,然后就试了一下,我的程序大概是取,时跑的最快。记得扫的时候不能重复算同一个数。

code

const
  size=67;
  qt=1500;
var
  n,c,m,i,j,ans,l,r,k,first,last:longint;
  a,b,st,ed,temp:array[1..100000]of longint;
  sum:array[1..qt,1..qt+1]of longint;
  flag:array[1..100000]of boolean;
     
procedure init;
begin
  for i:=1 to n do
    inc(ed[a[i]]);
  for i:=2 to c do
    inc(ed[i],ed[i-1]);
  st:=ed;
  for i:=n downto 1 do
    begin
      b[st[a[i]]]:=i;
      dec(st[a[i]]);
    end;
  for i:=1 to c do
    inc(st[i]);
  for i:=1 to qt do
    begin
      if (i-1)*size+1>n then
        break;
      fillchar(temp,sizeof(temp),0);
      k:=i;
      for j:=(i-1)*size+1 to n do
        begin
          inc(temp[a[j]]);
          if (temp[a[j]] and 1=0)and(temp[a[j]]>0) then
            inc(sum[i,k]);
          if (temp[a[j]] and 1=1)and(temp[a[j]]>1) then
            dec(sum[i,k]);
          if j mod size=0 then
            begin
              inc(k);
              sum[i,k]:=sum[i,k-1];
            end;
        end;
    end;
end;
     
function query(x,num:longint):longint;
var
  l,r:longint;
begin
  l:=st[num];
  r:=ed[num]+1;
  while l<r do
    if b[(l+r) shr 1]<=x then
      l:=(l+r) shr 1+1
    else
      r:=(l+r) shr 1;
  exit(l-st[num]);
end;
     
procedure modify(x:longint);
begin
  if flag[x] then
    exit;
  flag[x]:=true;
  k:=query(last*size,x)-query((first-1)*size,x);
  if (k and 1=0)and(k>0) then
    dec(ans);
  k:=query(r,x)-query(l-1,x);
  if (k and 1=0)and(k>0) then
    inc(ans);
end;
     
begin
  read(n,c,m);
  for i:=1 to n do
    read(a[i]);
  init;
  for m:=m downto 1 do
    begin
      read(l,r);
      l:=(l+ans) mod n+1;
      r:=(r+ans) mod n+1;
      if l>r then
        begin
          i:=l;
          l:=r;
          r:=i;
        end;
      ans:=0;
      for first:=qt+1 downto 2 do
        if l>(first-2)*size then
          break;
      for last:=0 to qt-1 do
        if r<(last+1)*size then
          break;
      if first>last then
        begin
          for j:=l to r do
            begin
              if flag[a[j]] then
                continue;
              flag[a[j]]:=true;
              k:=query(r,a[j])-query(l-1,a[j]);
              if (k and 1=0)and(k>0) then
                inc(ans);
            end;
          for j:=l to r do
            flag[a[j]]:=false;
          writeln(ans);
          continue;
        end;
      inc(ans,sum[first,last]);
      for j:=l to (first-1)*size do
        modify(a[j]);
      for j:=last*size+1 to r do
        modify(a[j]);
      for j:=l to (first-1)*size do
        flag[a[j]]:=false;
      for j:=last*size+1 to r do
        flag[a[j]]:=false;
      writeln(ans);
    end;
end.

bzoj3289 Mato的文件管理

题目就是要你求区间逆序对个数。首先留意到没有强制在线,爽!上莫队,用树状数组来维护当前区间内每个数的出现次数,在当前区间前面添加/删除时就把答案加上/减去比这个数小的数的数量,在区间后面的时候就加上/减去比这个数大的。当然第一种也是可行的,用主席树来维护区间出现次数,把预处理的答案加上中的元素造成的逆序对数即可。这两种做法的复杂度都是一样的,不过后者的实际效率大致是前者的2~3倍吧。第二、第三种分块的话空间128M可能还是太紧了吧……

code(莫队算法+树状数组)

{$inline on}
var
  n,q,i,j,size,t,sum,tot,last:longint;
  a,b,l,r,ans,num:array[0..50000]of longint;
  bit:array[1..1000000]of longint;
   
procedure swap(var x,y:longint);inline;
begin
  t:=x;
  x:=y;
  y:=t;
end;
   
procedure qsort_(l,r:longint);
var
  i,j,x:longint;
begin
  i:=l;
  j:=r;
  x:=a[b[(l+r) shr 1]];
  repeat
    while a[b[i]]<x do
      inc(i);
    while a[b[j]]>x do
      dec(j);
    if i<=j then
      begin
        swap(b[i],b[j]);
        inc(i);
        dec(j);
      end;
  until i>j;
  if i<r then
    qsort_(i,r);
  if l<j then
    qsort_(l,j);
end;
   
procedure qsort(ll,rr:longint);
var
  i,j,x,y:longint;
begin
  i:=ll;
  j:=rr;
  x:=l[(ll+rr) shr 1] div size;
  y:=r[(ll+rr) shr 1];
  repeat
    while (l[i] div size<x)or(l[i] div size=x)and(r[i]<y) do
      inc(i);
    while (l[j] div size>x)or(l[j] div size=x)and(r[j]>y) do
      dec(j);
    if i<=j then
      begin
        swap(l[i],l[j]);
        swap(r[i],r[j]);
        swap(num[i],num[j]);
        inc(i);
        dec(j);
      end;
  until i>j;
  if i<rr then
    qsort(i,rr);
  if ll<j then
    qsort(ll,j);
end;
   
function lowbit(x:longint):longint;inline;
begin
  exit(x and (-x));
end;
   
function query(x:longint):longint;
begin
  query:=0;
  while x>0 do
    begin
      inc(query,bit[x]);
      dec(x,lowbit(x));
    end;
end;
   
procedure modify(x,num:longint);
begin
  inc(sum,num);
  while x<=n do
    begin
      inc(bit[x],num);
      inc(x,lowbit(x));
    end;
end;
   
begin          
  read(n);
  for i:=1 to n do
    begin
      read(a[i]);
      b[i]:=i;
    end;
  qsort_(1,n);
  for i:=1 to n do
    if last=a[b[i]] then
      a[b[i]]:=tot
    else
      begin
        inc(tot);
        last:=a[b[i]];
        a[b[i]]:=tot;
      end;
  read(q);
  for i:=1 to q do
    begin
      read(l[i],r[i]);
      num[i]:=i;
    end;
  size:=trunc(sqrt(n));
  qsort(1,q);
  l[0]:=1;
  for i:=1 to q do
    begin
      if r[i-1]<l[i] then
        begin
          for j:=l[i-1] to r[i-1] do
            modify(a[j],-1);
          ans[num[i]]:=0;
          for j:=r[i] downto l[i] do
            begin
              inc(ans[num[i]],query(a[j]-1));
              modify(a[j],1);
            end;
        end
      else
        begin
          ans[num[i]]:=ans[num[i-1]];
          for j:=l[i-1] to l[i]-1 do
            begin
              dec(ans[num[i]],query(a[j]-1));
              modify(a[j],-1);
            end;
          for j:=l[i-1]-1 downto l[i] do
            begin
              inc(ans[num[i]],query(a[j]-1));
              modify(a[j],1);
            end;
          for j:=r[i-1] downto r[i]+1 do
            begin
              dec(ans[num[i]],sum-query(a[j]));
              modify(a[j],-1);
            end;
          for j:=r[i-1]+1 to r[i] do
            begin
              inc(ans[num[i]],sum-query(a[j]));
              modify(a[j],1);
            end;
        end;
    end;
  for i:=1 to q do
    writeln(ans[i]);
end.

Comments

comments powered by Disqus