首页 > 代码库 > 2009国家集训队小Z的袜子

2009国家集训队小Z的袜子

莫队算法?

感觉没什么优越性啊?难道就是因为在排序的时候cmp函数的不同?这样做为什么减少时限啊?

我带着疑惑敲了代码,却一直有bug……

代码:

 1 type node=record 2      l,r,id,x,y:int64; 3      end; 4 var a,ans:array[1..55000] of node; 5     s,c,p:array[1..55000] of longint; 6     i,n,m,block,l,r,k:longint; 7     anss:int64; 8 function gcd(x,y:longint):longint; 9  begin10  if y=0 then exit(x) else exit(gcd(y,x mod y));11  end;12 function cmp(x,y:node):boolean;13  begin14  if p[x.l]=p[y.l] then exit(x.r<y.r);15  exit(x.l<y.l);16  end;17 procedure sort(h,l:longint);18  var i,j:longint;19      tmp,mm:node;20  begin21   i:=h;j:=l;mm:=a[(i+j)>>1];22   repeat23     while cmp(a[i],mm) do inc(i);24     while cmp(mm,a[j]) do dec(j);25     if i<=j then26       begin27        tmp:=a[i];a[i]:=a[j];a[j]:=tmp;28        inc(i);dec(j);29       end;30   until i>j ;31   if i<l then sort(i,l);32   if j>h then sort(h,j);33  end;34 procedure init;35  begin36    readln(n,m);37    for i:=1 to n do read(c[i]);38    block:=trunc(sqrt(n));39    for i:=1 to n do p[i]:=(i-1) div block+1;40    for i:=1 to m do41     begin42       readln(a[i].l,a[i].r);43       a[i].id:=i;44     end;45  end;46 procedure update(p,add:longint);47  begin48   dec(anss,sqr(s[c[p]]));49   inc(s[c[p]],add);50   inc(anss,sqr(s[c[p]]));51  end;52 procedure main;53  begin54   sort(1,m);55   l:=1;r:=0;56   for i:=1 to m do57     begin58       while r<a[i].r do59         begin60          update(r+1,1);inc(r);61         end;62       while r>a[i].r do63         begin64          update(r,-1);dec(r);65         end;66       while l<a[i].l do67         begin68         update(l,-1);inc(l);69         end;70       while l>a[i].l do71         begin72         update(l-1,1);dec(l);73         end;74       if a[i].l=a[i].r then75         begin76          a[i].x:=0;a[i].y:=1;77          continue;78         end;79       with a[i] do80        begin81          x:=anss-(r-l+1);82          y:=(r-l+1)*(r-l);83          k:=gcd(x,y);84          x:=x div k;y:=y div k;85        end;86       end;87   for i:=1 to m do ans[a[i].id]:=a[i];88   for i:=1 to m do with ans[i] do writeln(x,/,y);89   end;90 begin91   init;92   main;93 end.              
View Code