要使用莫队算法前提 ，已知[l,r]的答案，要能在logn或者O(1)的时间得到[l+1,r],[l-1,r],[l,r-1],[l,r+1],适用于一类不修改的查询
优美的替代品——分块
将n个数分成sqrt(n)块
按区间排序，以左端点所在块内为第一关键字，右端点为第二关键字，进行排序
也就是以( pos [l],r )排序
然后搞就可以了
搞得过程是这样的：
一、i与i+1在同一块内，r单调递增，所以r是O(n)的。由于有n^0.5块,所以这一部分时间复杂度是n^1.5。
二、i与i+1跨越一块，r最多变化n，由于有n^0.5块，所以这一部分时间复杂度是n^1.5
三、i与i+1在同一块内时变化不超过n^0.5，跨越一块也不会超过2*n^0.5，不妨看作是n^0.5。由于有n个数，所以时间复杂度是n^1.5
于是就变成了O(n^1.5)了
——————————以上来自http://hzwer.com/2782.html，略有修改
黄学长的前两条说的是更新区间右端点r的复杂度是O(n^1.5)，这个说的很清楚；
最后一条说的的是更新区间左端点l的复杂度，我想略做添加
排序后的i和i+1个查询如果在同一块变化不超过sqrt(n),但是当跨越一块时，最大却不止是2*n^0.5,可以是n，
这样我们可以在每一个没有查询的块里添加一个辅助查询区间（l=该块的右界，r为下一个真正询问的右界 ），这样最多添加n^0.5这样的查询点 这样总的 查询个数是 n+n^0.5;
这样再应用黄学长第三条，i,i+1在一块，l不超过n^0.5，跨越一块（此时由于添加辅助查询点）最多是2*n^0.5
一共有n+n^0.5个查询 所以复杂度是 （n+n^0.5）*n^0.5=(n^0.5+1)n 所以复杂度是n^1.5
（添加辅助点不会变慢）
所以最后复杂度是O(n^1.5)
代码如下：（代码写的不好，如果要看还是看上述链接的比较好，以下仅供娱乐）
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<string>
#include<iostream>
#include<cstdlib>
#include<queue>
#include<map>
#include<set>
#include<cmath>
using namespace std;
typedef long long LL;
const int maxn=;
LL gcd(LL a, LL b)
{
if(a==)return b;
while(a%b)
{
LL t=a%b;
a=b;
b=t;
}
return b;
}
int num[maxn],pos[maxn],o[maxn];
LL ans=;
struct node
{
int l,r,id;
LL a,b;
} res[maxn];
bool cmp1(node x,node y)
{
if(pos[x.l]==pos[y.l])return x.r<y.r;
return x.l<y.l;
}
bool cmp2(node x,node y)
{
return x.id<y.id;
}
void change(int pos,int op)
{
LL t=num[o[pos]];
ans-=t*(t-)/;
num[o[pos]]+=op;
t=num[o[pos]];
ans+=t*(t-)/;
}
int main()
{
int n,m;
ans=;
scanf("%d%d",&n,&m);
int block=(int)(sqrt(n));
for(int i=; i<=n; ++i)
scanf("%d",&o[i]),pos[i]=(i-)/block+;
for(int i=; i<=m; ++i)
scanf("%d%d",&res[i].l,&res[i].r),res[i].id=i;
sort(res+,res+m+,cmp1);
for(int i=,l,r; i<=m; ++i)
{
if(i==)
for(int j=res[i].l; j<=res[i].r; ++j)
change(j,);
else
{
for(; r+<=res[i].r; ++r)
change(r+,);
for(; r>res[i].r; --r)
change(r,-);
for(; l<res[i].l; ++l)
change(l,-);
for(; l->=res[i].l; --l)
change(l-,);
}
l=res[i].l,r=res[i].r;
if(res[i].l==res[i].r)
{
res[i].a=;
res[i].b=;
continue;
}
res[i].a=ans;
LL t=res[i].r-res[i].l+;
res[i].b=t*(t-)/;
t=gcd(res[i].a,res[i].b);
res[i].a/=t;
res[i].b/=t;
}
sort(res+,res++m,cmp2);
for(int i=; i<=m; ++i)
printf("%lld/%lld\n",res[i].a,res[i].b);
return ;
}