# 莫队算法的模板

# 一、简介

莫队算法是由莫涛大神提出的一种区间操作的算法，这个算法的基础是分块和排序，整体复杂度为$O(n\sqrt x)$

这里不细讲莫队的原理细节，原理和细节请移步另一篇文章，上例题和代码

例题：小 Z 的袜子

Code:

#include <bits/stdc++.h>
using namespace std;
const int N=100001;
long long block,n,m,d[N],ans,answer[N][2],cnt[2*N],K;
struct node
{
	long long block_id,l,r,id;
	bool operator < (const node & ot) const
	{
		if(block_id==ot.block_id)
			return r<ot.r;
		return block_id<ot.block_id;
	}
}que[N],ys[N];
long long gcd(long long a,long long b)
{
    return b?gcd(b,a%b):a;
}
inline void read(long long & a)
{
    char ch;
    while(!(((ch=getchar())>='0')&&(ch<='9')));
    a=ch-'0';
    while(((ch=getchar())>='0')&&(ch<='9'))(a*=10)+=ch-'0';
}
void add(long long x)
{
	ans+=cnt[d[x]];
	cnt[d[x]]++;
	return;
}
void del(long long x)
{
	if(cnt[d[x]]>1)
		ans-=cnt[d[x]]-1;
	cnt[d[x]]--;
	return;
}
int main()
{
	read(n),read(m);
	for(long long i=1;i<=n;i++)
		read(d[i]);
	block=n/sqrt(m*2/3);
	for(long long i=1;i<=m;i++)
	{
		read(que[i].l),read(que[i].r);
		que[i].id=i;
		ys[i].l=que[i].l,ys[i].r=que[i].r;
		if(que[i].l%block==0)
			que[i].block_id=que[i].l/block;
		else
			que[i].block_id=que[i].l/block+1;
	}
	sort(que+1,que+1+m);
	long long l=1,r=0;
	for(long long i=1;i<=m;i++)
	{
		if(que[i].l==que[i].r)
			continue;
		while(l>que[i].l)
			add(--l);
		while(r<que[i].r)
			add(++r);
		while(l<que[i].l)
			del(l++);
		while(r>que[i].r)
			del(r--);
		answer[que[i].id][0]=ans,answer[que[i].id][1]=(que[i].r-que[i].l+1)*(que[i].r-que[i].l)/2;
	}
	for(long long i=1;i<=m;i++)
	{
		if(ys[i].l==ys[i].r)
		{
			printf("0/1\n");
			continue;
		}
		long long g=gcd(answer[i][0],answer[i][1]);
		if(answer[i][0]!=0)
			printf("%lld/%lld\n",answer[i][0]/g,answer[i][1]/g);
		else
			printf("0/1\n");
	}
	return 0;
}