莫队算法？
感觉没什么优越性啊？难道就是因为在排序的时候cmp函数的不同？这样做为什么减少时限啊？
我带着疑惑敲了代码，却一直有bug……
代码：
type node=record
l,r,id,x,y:int64;
end;
var a,ans:array[..] of node;
s,c,p:array[..] of longint;
i,n,m,block,l,r,k:longint;
anss:int64;
function gcd(x,y:longint):longint;
begin
if y= then exit(x) else exit(gcd(y,x mod y));
end;
function cmp(x,y:node):boolean;
begin
if p[x.l]=p[y.l] then exit(x.r<y.r);
exit(x.l<y.l);
end;
procedure sort(h,l:longint);
var i,j:longint;
tmp,mm:node;
begin
i:=h;j:=l;mm:=a[(i+j)>>];
repeat
while cmp(a[i],mm) do inc(i);
while cmp(mm,a[j]) do dec(j);
if i<=j then
begin
tmp:=a[i];a[i]:=a[j];a[j]:=tmp;
inc(i);dec(j);
end;
until i>j ;
if i<l then sort(i,l);
if j>h then sort(h,j);
end;
procedure init;
begin
readln(n,m);
for i:= to n do read(c[i]);
block:=trunc(sqrt(n));
for i:= to n do p[i]:=(i-) div block+;
for i:= to m do
begin
readln(a[i].l,a[i].r);
a[i].id:=i;
end;
end;
procedure update(p,add:longint);
begin
dec(anss,sqr(s[c[p]]));
inc(s[c[p]],add);
inc(anss,sqr(s[c[p]]));
end;
procedure main;
begin
sort(,m);
l:=;r:=;
for i:= to m do
begin
while r<a[i].r do
begin
update(r+,);inc(r);
end;
while r>a[i].r do
begin
update(r,-);dec(r);
end;
while l<a[i].l do
begin
update(l,-);inc(l);
end;
while l>a[i].l do
begin
update(l-,);dec(l);
end;
if a[i].l=a[i].r then
begin
a[i].x:=;a[i].y:=;
continue;
end;
with a[i] do
begin
x:=anss-(r-l+);
y:=(r-l+)*(r-l);
k:=gcd(x,y);
x:=x div k;y:=y div k;
end;
end;
for i:= to m do ans[a[i].id]:=a[i];
for i:= to m do with ans[i] do writeln(x,'/',y);
end;
begin
init;
main;
end.