前言

本文部分摘自洛谷

正文

a very very difficult problem,have a lot of 细节

对于这种题目，在线似乎没有什么有效的暴力，只能套用蒲公英中的分块暴力，但这题时限和内存都远远小于蒲公英，貌似不行。

把这题与蒲公英对比，发现他少了一个重要的约束：询问不一定在线！

于是我们考虑离线处理，怎么处理呢？暴力只能推到O(n^2),怎么办呢？

接下来就要引入主题————莫队算法:

其核心思维就是对于 区间查询 操作，通过对所有 “被询问的区间进行” 合理的排序 ，然后通过 暴力移动区间的左右端点 并 快速更新答案 得到所有询问的结果。

其算法流程主要是：

1.对于所有区间端点的移动，我们要设计出一种 O(1) 的方法使得我们可以快速维护移动端点后一个区间的答案。

2.有了这种方法之后，我们根据刚才的复杂度分析，我们对整个序列分块，每一块大小 $O(\sqrt{n})$

3.然后我们对所有询问的区间排序，排序完之后左端点每一次最多移动 $\sqrt{n} n$的距离总共 $n$ 次，右端点单调不降所以每一个块移动 $n$ 的距离总共 $\sqrt{n}n$次，所以总复杂度为 $O(n\sqrt{n})$

当然，莫队还有普通莫队，带修莫队(单点修改)，树上莫队，回滚莫队还用二次离线莫队，这里不多bb。

这里考虑对询问的左右区间下手，先按左端点升序排序，再在每个块里按右端点降序排序。这样子排序保证了一个很重要的性质：在每个分块里，右端点单调不递减，右端点最多变化 $n$ 次。而在区块内的左端点中，每次极限最多移动 $\sqrt n$次，最多 $\sqrt n$ ,共计n次。由于左端点和右端点单独移动时分开来算,所以一个分块时间复杂度为 $O(n)$,总时间复杂度为 $O(n\sqrt n)$.

然后计算的分母为(l-r+1)*（l-r+1-1)/2.也就是在 (l-r+1) 个数中取2个数。因为要去重，所以 /2.

然后分子单独计算。我们使用一个数组记录每个数出现的次数，一个变量来记录当前的值。在每次变化的时候，我们先要减去 (要加上或减去那个数所在的序号对答案的贡献)，更新以后再加上。

这真是一个神奇的算法~。莫队利用询问排序后的单调递增，保证右边和左边分开计算，再用分块暴力维护时间复杂度~。

单谈思想并没有太大难度，顶多是思路较难想到，但代码中有亿点点细节。

在程序的处理中，我们采用四个 while 循环来模拟询问的加加减减。分块只是为了排序，在实现中，我们可暂时忽略分块，直接整体做。

然后特别说明左右区间的移动情况。这里只谈论初始l=r=0的情况(详见代码)。因为他是这样运作的：

因此当l<e[i].l时为减,r<e[i].时为加.

特别留意发现，tl实际上时减不到L的，反之tr能加到R。

所以while(l>=e[i].l)add(a[l--]);中的=保证tl能减到L前。

#include<bits/stdc++.h>
#define int long long
using namespace std;
const int N=5e4+1e3;
int n,m,t,tot;
int pos[N],L[N],R[N],a[N],c[N];
struct node
{
    int l,r,id,ans;
}e[N];
bool mycmp1(node x,node y)
{
    return x.l<y.l;
}
bool mycmp2(node x,node y)
{
    return x.r<y.r;
}
bool mycmp3(node x,node y)
{
    return x.id<y.id;
}
void add(int x)
{
    tot=tot-(c[x])*max(0ll,c[x]-1)/2;c[x]++;
    tot=tot+c[x]*max(0ll,c[x]-1)/2; 
}
void dec(int x)
{
    tot=tot-(c[x])*max(0ll,c[x]-1)/2;c[x]--;
    tot=tot+c[x]*max(0ll,c[x]-1)/2;  
} 
void read()
{
    scanf("%lld%lld",&n,&m);
    for(int i=1;i<=n;i++)
        scanf("%lld",&a[i]);
    for(int i=1;i<=m;i++)
    {
        scanf("%lld%lld",&e[i].l,&e[i].r);
        e[i].id=i;
    }
} 
void pre()
{
    int w=sqrt(n);
    for(int i=1;i<=m;i+=w)
    {
        L[++t]=i,R[t]=min(m,i+w-1);
        for(int j=L[t];j<=R[t];j++)
            pos[j]=t;
    }
    sort(e+1,e+m+1,mycmp1);
    for(int i=1;i<=t;i++)
        sort(e+L[i],e+R[i]+1,mycmp2);
}
void work()
{
    tot=0;int l=0,r=0;
    for(int i=1;i<=m;i++)
    {
        while(l<e[i].l)dec(a[++l]);
        while(l>=e[i].l)add(a[l--]);
        while(r<e[i].r)add(a[++r]);
        while(r>e[i].r)dec(a[r--]);
        e[i].ans=tot;
    }
    sort(e+1,e+m+1,mycmp3);
}
void write()
{
    for(int i=1;i<=m;i++)
        if(!e[i].ans)puts("0/1");
        else
        {
            int q=e[i].r-e[i].l+1;
            int j=__gcd(e[i].ans,(q-1)*q/2);
            printf("%lld/%lld\n",e[i].ans/j,(q-1)*q/2/j);
         }
}
signed main()
{
    read();
    pre();
    work();
    write();
}