小Z的袜子 题解【莫队】【分块】【学习笔记】

点击量：209

    开始莫队入门了

目录

题目描述

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

 

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

 

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

 

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

 

输入输出格式

输入格式：

输入文件第一行包含两个正整数\(N\)和\(M\)。\(N\)为袜子的数量，\(M\)为小\(Z\)所提的询问的数量。接下来一行包含\(N\)个正整数\(C_i\)，其中\(C_i\)表示第\(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\le 5000\)；

 

\(60\%\)的数据中\(N,M\le 25000\)；

 

\(100\%\)的数据中\(N,M\le 50000,1\le L<R\le N,C_i\le N\)。

莫队算法：

简介：

    莫队是国家集训队爷莫涛提出的一种算法，它主要针对离线区间询问，可以在简单的代码复杂度（相对主席树等）以及合理的时间复杂度内（\(O(n\sqrt{n})\)）完成一些查询。

引入：

    对于袜子这道题，我们如果让区间随着询问在数列上移动（l、r指针每次只移动一个单位），那么查询的时间复杂度会很高，即使对其中一个端点排序也是如此。此时需要用到分块思想。

原理：

    我们把询问按照\(l\)为第一关键字排序，那么当相邻两个询问的\(r\)变化很大时，均摊时间复杂度还是会趋向\(O(n^2)\)。我们可以试着把询问按\(l\)所在的位置分成一些块，由基本不等式\((a+b\ge 2\sqrt{ab},a=b\Leftrightarrow a+b=2\sqrt{ab})\)知分块的大小为\(\sqrt{n}\)或\(\sqrt{m}\)是最优的。此时每个询问会属于一个块。

    这样我们在外部对所有询问进行排序，第一关键字是左端点所在块的编号升序，当块的编号相等时，按第二关键字右端点坐标升序。那么这时候对于一个块而言，右端点移动的距离是\(O(n)\)，块内理论有\(O(\sqrt{m})\)个询问，因此左端点最多移动\(\sqrt{mn}\)次，左右端点移动次数差不多，\(m,n\)同阶，统一看做是\(n\)，那么有\(O(\sqrt{m})=O(\sqrt{n})\)个块，每个块都有\(O(n)\)的移动左右端点复杂度，总时间复杂度就是\(O(n\sqrt{n})\)。

    此时可以尝试证明取根号是比较优的复杂度，设分块大小为\(L\)，则对于所有块左端点移动了最多\(mL\)，对于每个块右端点移动了\(n\)次，那么有\(\frac nL\)个这样的块，每次右端点移动\(n\)次，这时对于所有块的移动次数就是\(\frac {n^2}L\)那么这样的复杂度是\(\frac {n^2}L+mL\)，它是个双勾函数，依然用基本不等式可以推知\(L\)取\(\frac n{\sqrt{m}}\)最优。\(n,m\)同阶时直接取根号即可。

实现：

    首先按上面的方法排序，初始状态定义\(l=1,r=0\)，意思是当前询问区间为\([l,r]\)，每次\(l\)或\(r\)只移动一格，每次更改统计方案数时\(O(1)\)修改即可。对于题目的要求，询问区间出现相同袜子的概率就是

$$\frac{\sum_{i\in [l,r],app_{a_i}>1}app_i(app_i-1)}{(r-l+1)^2}$$。\(app_i\)表示这个颜色出现过多少次，直接当条件概率计算即可。此时答案只有一项，也不用通分，直接用\(\gcd\)约分即可。

Code：

#include<cmath>
#include<cstdio>
#include<cstring>
#include<algorithm>
struct query
{
    int l,r,b,i;
    long long up,down;
    friend bool operator <(query x,query y)
    {
        return x.b==y.b?x.r<y.r:x.l<y.l;
    }
}q[50500];
bool cmp(query x,query y)
{
    return x.i<y.i;
}
int a[50500],apr[50500];
int un;
long long sum=0;
void change(int x,int d)
{
    long long ori=apr[x]*(apr[x]-1);
    apr[x]+=d;
    sum+=apr[x]*(apr[x]-1)-ori;
}
long long gcd(long long x,long long y)
{
    if(!y)
        return x;
    return gcd(y,x%y);
}
int main()
{
    int n,m;
    scanf("%d%d",&n,&m);
    un=sqrt(m);
    for(int i=1;i<=n;++i)
        scanf("%d",&a[i]);
    for(int i=1;i<=m;++i)
    {
        q[i].i=i;
        scanf("%d%d",&q[i].l,&q[i].r);
        q[i].b=ceil((double)q[i].l/un);
    }
    std::sort(q+1,q+1+m);
    int l=1,r=0;
    for(int i=1;i<=m;++i)
    {
        if(q[i].l==q[i].r)
        {
            q[i].up=0;
            q[i].down=1;
            continue;
        }
        while(l<q[i].l)
            change(a[l++],-1);
        while(l>q[i].l)
            change(a[--l],1);
        while(r<q[i].r)
            change(a[++r],1);
        while(r>q[i].r)
            change(a[r--],-1);
        q[i].up=sum;
        q[i].down=(long long)(q[i].r-q[i].l+1)*(q[i].r-q[i].l);
        long long Gcd=gcd(q[i].up,q[i].down);
        q[i].up/=Gcd;
        q[i].down/=Gcd;
    }
    std::sort(q+1,q+1+m,cmp);
    for(int i=1;i<=m;++i)
        printf("%lld/%lld\n",q[i].up,q[i].down);
    return 0;
}