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天
发表回复