题解
莫队算法的一个典型应用。
对所有询问的左端点所在块的编号排序，块内对右端点排序，然后按顺序处理所有询问。由于$(l, r)$的情况可以在$O(1)$的情况下转移到$(l, r + 1), (l, r - 1), (l - 1, r), (l + 1, r)$的情况，因此根据一定的复杂度分析，该算法的时间复杂度是$O(n \sqrt{n})$。1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
using namespace std;
typedef long long ll;
struct Q{
ll l,r,sqi,id;
};
bool cmp(Q u,Q v){
if(u.sqi==v.sqi)return u.r<v.r;
return u.sqi<v.sqi;
}
Q query[50005];
ll a[50005],ans[50005][2],n,m,size;
ll cnt[50005]={0},tot=0;
ll sqr(ll t){return t*t;}
void update(ll o,ll id){
tot-=sqr(cnt[a[id]]),
cnt[a[id]]+=o,
tot+=sqr(cnt[a[id]]);
}
ll gcd(ll a,ll b){
return (!b)?a:gcd(b,a%b);
}
void init(){
ll i,j;
scanf("%lld%lld",&n,&m);
for(size=1;size*size<n;size++);
for(i=1;i<=n;i++)
scanf("%lld",&a[i]);
for(i=1;i<=m;i++)
scanf("%lld%lld",&query[i].l,&query[i].r),
query[i].sqi=(query[i].l-1)/size,
query[i].id=i;
sort(query+1,query+m+1,cmp);
}
void solve(){
ll L=1,R=0,_l,_r,_id,fz,fm,p;
for(int i=1;i<=m;i++){
_l=query[i].l,_r=query[i].r;
_id=query[i].id;
for(;R<_r;R++)
update(1,R+1);
for(;R>_r;R--)
update(-1,R);
for(;L<_l;L++)
update(-1,L);
for(;L>_l;L--)
update(1,L-1);
if(_l==_r){
ans[_id][0]=0,ans[_id][1]=1;
continue;
}
fz=tot-(_r-_l+1),fm=(_r-_l+1)*(_r-_l);
p=gcd(fm,fz);
fz/=p,fm/=p;
ans[_id][0]=fz,ans[_id][1]=fm;
}
for(int i=1;i<=m;i++)
printf("%lld/%lld\n",ans[i][0],ans[i][1]);
}
int main(){
init();
solve();
return 0;
}