Article From:https://www.cnblogs.com/MisakaAzusa/p/9061487.html

``````#include <cstdio>
#include <algorithm>
#include <iostream>
#include <cmath>
using namespace std;
const int maxn =  50000+10;
{
long long k=0;
char c;
c=getchar();
while(!isdigit(c))c=getchar();
while(isdigit(c)){k=(k<<3)+(k<<1)+c-'0';c=getchar();}
return k;
}
long long n, m, bl, answer, curL = 1, curR = 0, cnt[maxn], a[maxn], gg;

struct query{
long long p, l, r;
}e[maxn];

long long x, y;
}ans[maxn], now;

long long gcd(long long x, long long y)
{
if(x%y == 0) return y;
else return gcd(y,x%y);
}

bool cmp(query a, query b)
{
return (a.l/bl) == (b.l/bl) ? a.r < b.r : a.l < b.l;
}

{
cnt[a[pos]]++;
if(cnt[a[pos]] > 1)
now.x = now.x + cnt[a[pos]]*(cnt[a[pos]]-1)-(cnt[a[pos]]-1)*(cnt[a[pos]]-2);

}

void remove(long long pos)
{
cnt[a[pos]]--;
if(cnt[a[pos]] > 0)
now.x = now.x + cnt[a[pos]]*(cnt[a[pos]]-1)-(cnt[a[pos]]+1)*cnt[a[pos]];
}

int main()
{

bl = sqrt(n);

for(long long i = 1; i <= n; i++)

for(long long i = 1; i <= m; i++)
{
}

sort(e+1,e+1+m,cmp);

for(long long i = 1; i <= m; i++)
{
long long L = e[i].l, R = e[i].r;
while(curL < L)
remove(curL++);
while(curL > L)
while(curR < R)
while(curR > R)
remove(curR--);
now.y = (e[i].r-e[i].l+1)*(e[i].r-e[i].l);
if (!now.x)
{
now.x=0;
now.y=1;
}
gg = gcd(now.x, now.y);
ans[e[i].p].x = now.x/gg;
ans[e[i].p].y = now.y/gg;
}
for(long long i = 1; i <= m; i++)
printf("%lld/%lld\n",ans[i].x,ans[i].y);
return 0;
}``````