首页 > 代码库 > 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.
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。