题目描述
作为一个生活散漫的人，小Z每天早上都要耗费很久从一堆五颜六色的袜子中找出一双来穿。终于有一天，小Z再也无法忍受这恼人的找袜子过程，于是他决定听天由命……

具体来说，小Z把这N只袜子从1到N编号，然后从编号L到R(L 尽管小Z并不在意两只袜子是不是完整的一双，甚至不在意两只袜子是否一左一右，他却很在意袜子的颜色，毕竟穿两只不同色的袜子会很尴尬。

你的任务便是告诉小Z，他有多大的概率抽到两只颜色相同的袜子。当然，小Z希望这个概率尽量高，所以他可能会询问多个(L,R)以方便自己选择。

然而数据中有L=R的情况，请特判这种情况，输出0/1。

输入格式
输入文件第一行包含两个正整数N和M。N为袜子的数量，M为小Z所提的询问的数量。接下来一行包含N个正整数Ci，其中Ci表示第i只袜子的颜色，相同的颜色用相同的数字表示。再接下来M行，每行两个正整数L，R表示一个询问。

输出格式
包含M行，对于每个询问在一行中输出分数A/B表示从该询问的区间[L,R]中随机抽出两只袜子颜色相同的概率。若该概率为0则输出0/1，否则输出的A/B必须为最简分数。（详见样例）

输入输出样例
输入 #1 复制
6 4
1 2 3 3 3 2
2 6
1 3
3 5
1 6
输出 #1 复制
2/5
0/1
1/1
4/15
说明/提示
30%的数据中 N,M ≤ 5000；

60%的数据中 N,M ≤ 25000；

100%的数据中 N,M ≤ 50000，1 ≤ L < R ≤ N，Ci ≤ N。

比较经典的一道莫队了。（我好菜QWQ）

考虑维护信息：这个计算概率应该挺简单，就是一个古典概率。区间长度已知，也就是我们需要取的物品总数已知。然后概率的分母就确定了。然后分子就是每个物品对应的组合数C，取2个。

add：设原来为x个，那么增加一个之后，增加的值为：[(x+1) * (x) - (x) * (x-1)] / 2 = x ，所以增加的就是原来的个数。

del：设原来为x个，那么减少一个之后，减少的值为：[(x) * (x-1) - (x-1) * (x-2)] / 2 = x-1 。

然后维护就很简单啦！！！最后注意特判L = R的情况，和化简。

AC代码：

#pragma GCC optimize(2)
#include<bits/stdc++.h>
#define int long long
using namespace std;
const int N=5e4+10;
int a[N],cnt[N],s,res1[N],res2[N],cl,cr,n,m,bl;
struct node{
	int l,r,id;
}t[N];
int cmp(const node &s1,const node &s2){
	return (s1.l/bl==s2.l/bl)?(s1.r<s2.r):(s1.l<s2.l);
}
inline void add(int x){
	s+=cnt[a[x]]++;
}
inline void del(int x){
	s-=--cnt[a[x]];	
}
signed main(){
	scanf("%lld %lld",&n,&m);	bl=sqrt(n);
	for(int i=1;i<=n;i++)	scanf("%lld",&a[i]);
	for(int i=1;i<=m;i++)	scanf("%lld %lld",&t[i].l,&t[i].r),t[i].id=i;
	sort(t+1,t+1+m,cmp);	cl=1;
	for(int i=1;i<=m;i++){
		int L=t[i].l;	int R=t[i].r;
		while(cl<L)	del(cl++);
		while(cl>L)	add(--cl);
		while(cr>R)	del(cr--);
		while(cr<R)	add(++cr);
		int fm=(R-L+1)*(R-L)/2;
		if(L==R){
			res1[t[i].id]=0;	res2[t[i].id]=1;	continue;
		}
		int gcd=__gcd(s,fm);	res1[t[i].id]=s/gcd;	res2[t[i].id]=fm/gcd;
	}
	for(int i=1;i<=m;i++)	printf("%lld/%lld\n",res1[i],res2[i]);
	return 0;
}