莫队
话说这国家集训队的题目应该是老题,比较水。
其它大佬已经说出了需要求出的东西:
\(\frac{(num[1]^2+num[2]^2+num[3]^2...num[n]^2-(R-L+1))}{(R-L+1)*(R-L)}\)的最简单形态。其中\(num[i]\)表示一个数字的出现次数。
而我们只需要求出\(num[1]^2+num[2]^2+num[3]^2...num[n]^2\)。莫队可以实现每一个数字的出现次数,然后每次统计答案的时候注意一下。记得答案要最简模式,所以要用\(GCD\),注意\(l=r\)的情况。
最后告诉大家一个好东西,在用莫队时,一个块的数量最好是\(\frac{N}{15}\)~\(\frac{N}{20}\)。如果只是单纯的打\(\sqrt{N}\),你可能会超时。对于\(Pascal\)选手,这两个的差别将近\(1s\)。
\(Code\)
// luogu-judger-enable-o2
var
node_num,i,j,n,m,l,r:longint;
num:array[-1..510000] of int64;
id,left,right,recf:array[-1..510000] of int64;
bucket:array[-1..1010007] of int64;
ans:array[1..2,-1..510000] of int64;
p,k,sum:int64;
procedure Sort(l,r:longint);
var
i,j,s,t:longint;
begin
i:=l; j:=r; s:=(l+r) div 2;
repeat
while ((recf[i]<recf[s])or((recf[i]=recf[s])and(right[i]<right[s]))) do inc(i);
while ((recf[j]>recf[s])or((recf[j]=recf[s])and(right[j]>right[s]))) do dec(j);
if i<=j then
begin
t:=recf[i]; recf[i]:=recf[j]; recf[j]:=t;
t:=id[i]; id[i]:=id[j]; id[j]:=t;
t:=left[i]; left[i]:=left[j]; left[j]:=t;
t:=right[i]; right[i]:=right[j]; right[j]:=t;
inc(i); dec(j);
end;
until i>=j;
if i<r then Sort(i,r);
if j>l then Sort(l,j);
end;
function Locate(node:longint):longint;
begin
if node mod node_num=0 then
exit(node div node_num);
exit(node div node_num+1);
end;
procedure Ready;
begin
read(n,m);
node_num:=n div 17;
for i:=1 to n do read(num[i]);
for i:=1 to m do
begin id[i]:=i; read(left[i],right[i]); recf[i]:=Locate(left[i]); end;
Sort(1,m);
end;
procedure add(x:longint);
begin
dec(sum,bucket[x]*bucket[x]);
inc(bucket[x]);
inc(sum,bucket[x]*bucket[x]);
end;
procedure dim(x:longint);
begin
dec(sum,bucket[x]*bucket[x]);
dec(bucket[x]);
inc(sum,bucket[x]*bucket[x]);
end;
function gcd(a_,b_:int64):int64;
var
a,b,c:int64;
begin
a:=a_;
b:=b_;
repeat
c:=a mod b;
a:=b;
b:=c;
until b=0;
exit(a);
end;
begin
Ready;
l:=1;
r:=0;
for i:=1 to m do
begin
while r<right[i] do begin inc(r); add(num[r]); end;
while r>right[i] do begin dim(num[r]); dec(r); end;
while l<left[i] do begin dim(num[l]); inc(l); end;
while l>left[i] do begin dec(l); add(num[l]); end;
if left[i]=right[i] then
begin
ans[1,id[i]]:=0;
ans[2,id[i]]:=1;
end
else
begin
p:=(right[i]-left[i]+1)*(right[i]-left[i]);
k:=gcd((sum-(right[i]-left[i]+1)),p);
ans[1,id[i]]:=(sum-(right[i]-left[i]+1)) div k;
ans[2,id[i]]:=p div k;
end;
end;
for i:=1 to m do
writeln(ans[1,i],'/',ans[2,i]);
end.