题解 P1494 【[国家集训队]小Z的袜子】

lemir3 · 2019-08-01 20:07:19 · 题解

获得更好的阅读体验

题面

很容易看出来是莫队的题.

题目分析

给出n个数和m个区间,要求统计任意取出区间内的两个数相等的概率.

概率很好算,只要求出区间内每个数字出现的次数,用次数来求出能取出的方案数,以及整个区间能够取得方案数就可以了.

题目要求通分,用欧几里得算法求gcd就可以了.

函数如下:

inline lxl gcd(lxl x,lxl y)
{
    return y?gcd(y,x%y):x;
}

然后同志们再来考虑如何使用莫队进行统计.

因为是在区间内取出两个数,设某个数字出现的次数为a,能够取出的方案数为b,根据乘法原理,我们可以得出如下式子:

b_1=a\*(a-1)/2

在删去一个数时,a要减上1,式子变为:

b_2=(a-1)\*(a-2)/2

展开,可以得出:

b_2=b_1-(a-1)

同理,在加上一个数时,可以得到:

b_2=b_1+a

所以我们就可以写出莫队的转移函数了:

inline void delete_(lxl id)
{
    tot[num[id]]--;
    if(tot[num[id]]>0)
    {
        cnt=cnt-tot[num[id]];
    }
}

inline void add(lxl id)
{
    tot[num[id]]++;
    if(tot[num[id]]>1)
    {
        cnt=cnt+(tot[num[id]]-1);
    }
}

其他内容也就是一个寻常的莫队了.

代码

#include "cstdio"
#include "cstring"
#include "algorithm"
#include "cmath"
#include "iostream"

#define lxl long long
#define debug(x) printf("debug:%lld\n",x)

using namespace std;

lxl n,m,len,CurL,CurR,cnt;
lxl tot[500010],num[500010],ans[500010],QLen[500010];

struct QUERY
{
    lxl l,r,id;
}q[50010];

inline bool cmp(QUERY d1,QUERY d2)
{
    return (d1.l/len==d2.l/len)?d1.r<d2.r:d1.l<d2.l;
}

inline lxl clac(lxl);
inline void delete_(lxl);
inline void add(lxl);
inline lxl gcd(lxl,lxl);

signed main(void)
{
//  freopen("testdata.in","r",stdin);
//  freopen("test.out","w",stdout);
    scanf("%lld%lld",&n,&m);
    len=n/sqrt(m*2/3);
    for(lxl _=1;_<=n;_++)
    {
        scanf("%lld",num+_);
    }
    for(lxl _=1;_<=m;_++)
    {
        lxl l,r;
        scanf("%lld%lld",&l,&r);
        QLen[_]=r-l+1;
        q[_].l=l;
        q[_].r=r;
        q[_].id=_;
//      debug(QLen[_]);
    }
    sort(q+1,q+1+m,cmp);
/*  for(lxl _=1;_<=m;_++)
    {
        debug(q[_].id);
    }*/
    CurL=CurR=q[1].l;
    tot[num[CurL]]++;
    for(lxl _=1;_<=m;_++)
    {
        lxl l=q[_].l;
        lxl r=q[_].r;
        lxl IDQuery=q[_].id;
        while(CurL<l)
        {
            delete_(CurL++);
//          debug(CurL);
//          debug(cnt);
        }
        while(CurL>l)
        {
            add(--CurL);
//          debug(CurL);
//          debug(cnt);
        }
        while(CurR<r)
        {
            add(++CurR);
//          debug(CurR);
//          debug(cnt);
        }
        while(CurR>r)
        {
            delete_(CurR--);
//          debug(CurR);
//          debug(cnt);
        }
        ans[IDQuery]=cnt;
    }
    for(lxl _=1;_<=m;_++)
    {
        if(ans[_]==0||QLen[_]==1)
        {
            printf("0/1\n");
            continue;
        }
        lxl len_=QLen[_]*(QLen[_]-1)/2;
        lxl gcd_=gcd(ans[_],len_);
        printf("%lld/%lld\n",ans[_]/gcd_,len_/gcd_);
    }
return 0;
}

/*
inline lxl clac(lxl id)
{
    if(tot[num[id]]==0||tot[num[id]]==1)
    {
        return 0;
    }
return tot[num[id]]*(tot[num[id]]-1)/2;
}
*/

inline void delete_(lxl id)
{
    tot[num[id]]--;
    if(tot[num[id]]>0)
    {
        cnt=cnt-tot[num[id]];
    }
}

inline void add(lxl id)
{
    tot[num[id]]++;
    if(tot[num[id]]>1)
    {
        cnt=cnt+(tot[num[id]]-1);
    }
}

inline lxl gcd(lxl x,lxl y)
{
    return y?gcd(y,x%y):x;
}