bzoj2038: [2009国家集训队]小Z的袜子(hose)【莫队算法】

  • 内容
  • 评论
  • 相关

第一道莫队题目Orz


题目点击这里

准备GDOI了。。。想起来有个叫做莫队的神奇东西,于是小小地涉猎了一点点,感觉学到了一点理念,关于离线和文明地暴力的。。。


题目模型很明确,很容易可以想到并简化成下面的形式:

用c[i]代表区间中颜色i的数量,那么对于区间[l,r]来说,成功率就是

∑(c[i]*(c[i]-1)/2)/((r-l+1)*(r-l)/2)

=∑(c[i]^2-c[i])/((r-l+1)*(r-l))

=(∑(c[i]^2)-(r-l+1))/((r-l+1)*(r-l))

那么题目就相当于维护区间内∑(c[i]^2)的值了。

首先在这里简单介绍一下莫队算法吧:

如果题目要求维护一个区间的某些东西,而如果我们可以通过[l,r]的值用O(1)的时间推出[l-1,r][l+1,r][l,r-1][l,r+1]的值,那么我们就可以先把所有的询问先读入进来,然后将N个数分为√N块,对读入的l按照块数,以r为第二关键字排序,就可以在O(N√N)的时间内解决问题。

证明还算比较容易:

1、对于l的处理,如果前后的值在同一个块内,那么最多只需要√N步可以推出新的l的值。如果不在同一块内,由于已经将l所分布的块进行排序,所以l的跨区间查询不会超过√N次,每次最多需要2√N步,所以均摊时间足够。

2、对于r,因为对同一块的l来说r是递增的,所以在l没有改变块之前r最多进行N次改变,一共有√N块,所以整个算法的总时间是O(N√N)的。

有了莫队算法的基础那么这道题就不是问题了。。。


代码:

{$inline on}
var
  num,up,dn,c,p:array[0..50000] of longint;
  a:array[0..50000,1..3]of longint;
  n,m,i,j,l,r,block,ans:longint;
  k,t:int64;
procedure sort(l,r:longint);
var
  i,j,x,y,k:longint;
begin
  if (l=29769) and (r=29776) then
  i:=i;
  i:=l;
  j:=r;
  x:=p[a[(l+r) div 2,1]];
  y:=a[(l+r) shr 1,2];
  repeat
    while (p[a[i,1]]<x) or (p[a[i,1]]=x) and (a[i,2]<y) do
    begin
      inc(i);
    end;
    while (x<p[a[j,1]]) or (p[a[j,1]]=x) and (a[j,2]>y) do
    begin
      dec(j);
    end;
    if not(i>j) then
    begin
      a[0]:=a[i];
      a[i]:=a[j];
      a[j]:=a[0];
      inc(i);
      j:=j-1;
    end;
  until i>j;
  if l<j then
  sort(l,j);
  if i<r then
  sort(i,r);
end;
procedure update(x,d:longint); inline;
begin
  ans:=ans-num[c[x]]*num[c[x]];
  num[c[x]]:=num[c[x]]+d;
  ans:=ans+num[c[x]]*num[c[x]];
end;
function gcd(x,y:int64):int64;
begin
  if x mod y=0 then exit(y)
  else exit(gcd(y,x mod y));
end;
begin
  //randomize;
  read(n,m);
  block:=trunc(sqrt(n));
  for i:=1 to n do
  begin
    read(c[i]);
    //c[i]:=random(n)+1;
    p[i]:=(i-1) div block;
  end;
  for i:=1 to m do
  begin
    read(a[i,1],a[i,2]);
    {a[i,1]:=random(n)+1;
    a[i,2]:=random(n)+1;
    if a[i,2]<a[i,1] then
    begin
      ans:=a[i,1];
      a[i,1]:=a[i,2];
      a[i,2]:=ans;
    end;}
    a[i,3]:=i;
  end;
  sort(1,m);                    
  l:=1;
  r:=0;
  ans:=0;
  for i:=1 to m do
  begin
    if r<a[i,2] then
    for j:=r+1 to a[i,2] do
    update(j,1);
    if r>a[i,2] then
    for j:=r downto a[i,2]+1 do
    update(j,-1);
    r:=a[i,2];
    if l<a[i,1] then
    for j:=l to a[i,1]-1 do
    update(j,-1);
    if l>a[i,1] then
    for j:=l-1 downto a[i,1] do
    update(j,1);
    l:=a[i,1];
    ans:=ans-a[i,2]+a[i,1]-1;
    if ans=0 then
    begin
      up[a[i,3]]:=0;
      dn[a[i,3]]:=1;
      ans:=ans+a[i,2]-a[i,1]+1;
      continue;
    end;
    k:=a[i,2]-a[i,1]+1;
    k:=k*(k-1);
    t:=gcd(ans,k);
    up[a[i,3]]:=ans div t;
    dn[a[i,3]]:=k div t;
    ans:=ans+a[i,2]-a[i,1]+1;
  end;
  for i:=1 to m do writeln(up[i],'/',dn[i]);
end.

ps:然而这题我一开始疯狂TLE,原来发现在排序交换的时候把每个点对应分块的位置也交换了。。。果然我还是太逗了
退役倒计时:29天

评论

0条评论

发表评论

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

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