$O(n\sqrt{n}+m\sqrt{n}\log V)$ 应该能过啊

#include<bits/stdc++.h>
#define int long long
using namespace std;
const int N=5e4+5,V=5e4;
int L[N],R[N],pos[N],a[N],ansx[N],ansy[N];
struct query{int l,r,id;}q[N];
bool cmp(query q1,query q2){return pos[q1.l]!=pos[q2.l]?pos[q1.l]<pos[q2.l]:q1.r<q2.r;}
int sum[N<<2],biome[N<<2];
void pushup(int p)
{
	sum[p]=sum[p<<1]+sum[p<<1|1];
	biome[p]=biome[p<<1]+biome[p<<1|1];
}
void update(int p,int pl,int pr,int x,int d)
{
	if(x<pl||pr<x)
		return ;
	if(x==pl&&x==pr)
	{
		sum[p]+=d;
		biome[p]=sum[p]*(sum[p]-1);
		return ;
	}
	int mid=(pl+pr)>>1;
	update(p<<1,pl,mid,x,d);
	update(p<<1|1,mid+1,pr,x,d);
	pushup(p);
}
//int qsum1(int p,int pl,int pr,int L,int R)
//{
//	if(R<pl||pr<L)
//		return 0;
//	if(L<=pl&&pr<=R)
//		return sum[p];
//	int mid=(pl+pr)>>1;
//	return qsum1(p<<1,pl,mid,L,R)+qsum1(p<<1|1,mid+1,pr,L,R);
//}
//int qsum2(int p,int pl,int pr,int L,int R)
//{
//	if(R<pl||pr<L)
//		return 0;
//	if(L<=pl&&pr<=R)
//		return biome[p];
//	int mid=(pl+pr)>>1;
//	return qsum2(p<<1,pl,mid,L,R)+qsum2(p<<1|1,mid+1,pr,L,R);
//}
signed main()
{
	ios::sync_with_stdio(false);
	cin.tie(0);
	int n,m;
	cin>>n>>m;
	int t=sqrt(n);
	for(int i=1;i<=n;++i)
		cin>>a[i];
	for(int i=1;i<=m;++i)
		cin>>q[i].l>>q[i].r,q[i].id=i;
	for(int i=1;i<=t;++i)
		for(int j=L[i];j<=R[i];++j)
			pos[j]=i;
	sort(q+1,q+m+1,cmp);
	int l=1,r=0;
	for(int i=1;i<=m;++i)
	{
		while(l<q[i].l)
			update(1,1,V,a[l],-1),++l;
		while(r>q[i].r)
			update(1,1,V,a[r],-1),--r;
		while(l>q[i].l)
			--l,update(1,1,V,a[l],1);
		while(r<q[i].r)
			++r,update(1,1,V,a[r],1);
		if(l==r)
		{
			ansx[q[i].id]=0;
			ansy[q[i].id]=1;
			continue;
		}
		int x=biome[1],y=(sum[1]*(sum[1]-1));
		ansx[q[i].id]=x/__gcd(x,y);
		ansy[q[i].id]=y/__gcd(x,y);
	}
	for(int i=1;i<=m;++i)
		cout<<ansx[i]<<'/'<<ansy[i]<<'\n';
}