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

作者: wjyyy 分类: 分块,区间统计,学习笔记,莫队,解题报告 发布时间: 2018-10-14 15:38

点击量:20

 

 

    开始莫队入门了

 

题目描述

作为一个生活散漫的人,小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;
}

 

1
说点什么

avatar
1 Comment threads
0 Thread replies
0 Followers
 
Most reacted comment
Hottest comment thread
0 Comment authors
Recent comment authors
  Subscribe  
最新 最旧 得票最多
提醒
trackback

[…] 【莫队学习笔记】 […]

/* */