[国家集训队]小Z的袜子（莫队）

[国家集训队]小Z的袜子

题目描述

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

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

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

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

输入格式：

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

输出格式：

包含M$M$行，对于每个询问在一行中输出分数A/B$A/B$表示从该询问的区间[L$L$,R$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

$$
$$
$$
$$
$$
$$

解：

这是一道莫队的板子题，所以我们来学波莫队。要是你当时就会莫队，那你就可以把这道数据结构套数据结构啥的题水过去了（不过好像当时没有莫队）。
其实莫队很暴力，不过它要满足几个条件：
1.离线，在线就滚粗（不过可以支持修改）
2.询问在[l$l$，r$r$]到[l$l$+1,r$r$]、[l$l$,r$r$+1]等比较好转移

那么为什么满足这个条件就可以过么，我们画个图理解一下：

看到这个魔性的图没？这就是奇奇怪怪的莫队算法
我们可以先想象把所有询问放到一个平面里，然后依次回答询问。然后我们证明一下复杂度。假设我们以n−−√$\sqrt{n}$分块，如上图，先把块相同的分到一起，然后相同块呢？我们按照从小到大排序。然后我们可以发现横着走点到点的长度不超过n−−√$\sqrt{n}$。然后竖着走了(块的个数*2*n的长度)。块的个数也是n−−√$\sqrt{n}$。
所以我们最坏走的长度是n∗n−−√$n\ast \sqrt{n}$。
然后怎么走？
要知道我们只有一步一步走，最好让每走一步的复杂度最小。O(1)$O(1)$啥的最好。

然后我们开始看这道题：
同样的，我们把所有询问放进一个平面里。然后考虑加一个点进去。某一种袜子的颜色加一，假设它现在颜色的个数为n$n$。

所以我们可以做到O(1)$O(1)$转移咯（去掉一个同理），贴一波代码：

#include<iostream>  
#include<cstdio>  
#include<cstring>  
#include<algorithm>  
using namespace std;  
long long n,m;  
long long col[50005],data[50005],k=300,l=1,r=1;//k为块大小  
long long ans;//只用计算分子，分母为  区间个数*（区间个数-1）  
long long mu[50005],zi[50005];  
struct lxy{  
    long long id,l,r;  
    long long ans;  
    bool operator < (const lxy &a)const//按块编号从小到大为第一关键字，按l从小到大为第二关键字  
    {  
        if(l/k==a.l/k) return r<a.r;  
        return l/k<a.l/k;  
    }  
}b[50005];  

long long gcd(long long x,long long y)//求个gcd约分  
{  
    if(x==0) return y;  
    return gcd(y%x,x);  
}  

void w()//上走  
{     
    col[data[l]]--;  
    ans-=col[data[l]]*2;l++;  
}  
void a()//左走  
{  
    col[data[r]]--;  
    ans-=col[data[r]]*2;r--;  
}  
void s()//下走  
{  
    l--;ans+=col[data[l]]*2;  
    col[data[l]]++;  
}  
void d()//右走  
{  
    r++;ans+=col[data[r]]*2;  
    col[data[r]]++;  
}  

int main()  
{  
    scanf("%lld%lld",&n,&m);  
    for(int i=1;i<=n;i++) scanf("%lld",&data[i]);  
    for(int i=1;i<=m;i++) scanf("%lld%lld",&b[i].l,&b[i].r),b[i].id=i;  
    sort(b+1,b+1+m);  
    col[data[1]]++;  
    for(int i=1;i<=m;i++)  
    {  
        while(r<b[i].r) d();  
        while(l>b[i].l) s();  
        while(r>b[i].r) a();  
        while(l<b[i].l) w();  
        b[i].ans=ans;  
    }  
    for(int i=1;i<=m;i++)  
    {  
        if(b[i].ans==0||b[i].l==b[i].r)//特殊情况特判  
        {  
          mu[b[i].id]=1;  
          zi[b[i].id]=0;  
        }  
        else//算算gcd，约约分  
        {  
          long long p;  
          p=gcd(b[i].ans,(b[i].r-b[i].l+1)*(b[i].r-b[i].l));  
          zi[b[i].id]=b[i].ans/p;  
          mu[b[i].id]=(b[i].r-b[i].l+1)*(b[i].r-b[i].l)/p;  
        }  
    }  
    for(int i=1;i<=m;i++) printf("%lld/%lld\n",zi[i],mu[i]);  
}