M_sea

洛谷1494 [国家集训队]小Z的袜子
LuoguBZOJ分析莫队。假如第$i$种袜子有$cnt[i]$个,那么抽到一双的概率是然后总的方案数是$C_{l...
扫描右侧二维码阅读全文
17
2018/12

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

Luogu

BZOJ

分析

莫队。

假如第$i$种袜子有$cnt[i]$个,那么抽到一双的概率是

$$\sum\limits_{i=1}^{n}C_{cnt[i]}^2$$

然后总的方案数是$C_{len}^2$。

概率就是:

$\frac{\sum\limits_{i=1}^n\,cnt[i]\cdot(cnt[i]-1)}{len(len-1)}$

莫队维护一下分子就行。

考虑一下$cnt[i]$增加/减少时答案发生了什么变化。大力推一发可以发现增加/减少了$2\cdot cnt[i]$。

细节见代码。

代码

#include <algorithm>
#include <iostream>
#include <cstdlib>
#include <cstring>
#include <cstdio>
#include <cmath>
#define re register
typedef int mainint;
#define int long long
using namespace std;

inline int read() {
    int X=0,w=1; char c=getchar();
    while (c<'0'||c>'9') { if (c=='-') w=-1; c=getchar(); }
    while (c>='0'&&c<='9') X=X*10+c-'0',c=getchar();
    return X*w;
}

const int MAXN=50000+10;

struct query { int l,r,id,len; } q[MAXN];
int a[MAXN],cnt[MAXN];
int block,ans=0;

inline int cmp(query a,query b) {
    return (a.l/block)^(b.l/block)?a.l<b.l:(((a.l/block)&1)?a.r<b.r:a.r>b.r);
}

inline void add(int x) {
    if (cnt[x]) ans+=(cnt[x]<<1);
    ++cnt[x];
}
inline void del(int x) {
    --cnt[x];
    if (cnt[x]) ans-=(cnt[x]<<1);
}

int Ans1[MAXN],Ans2[MAXN]; //分子、分母

inline int gcd(int a,int b) { return a%b?gcd(b,a%b):b; }

mainint main() {
    int n=read(),m=read(); block=n/sqrt(m);
    for (re int i=1;i<=n;++i) a[i]=read();
    for (re int i=1;i<=m;++i) {
        q[i].l=read(),q[i].r=read();
        q[i].id=i,q[i].len=q[i].r-q[i].l+1;
    }
    sort(q+1,q+m+1,cmp);
    int l=1,r=0;
    for (re int i=1;i<=m;++i) {
        int ql=q[i].l,qr=q[i].r,id=q[i].id;
        while (l<ql) del(a[l++]);
        while (l>ql) add(a[--l]);
        while (r<qr) add(a[++r]);
        while (r>qr) del(a[r--]);
        if (ql==qr) { Ans1[id]=0,Ans2[id]=1; continue; }
        Ans1[id]=ans,Ans2[id]=q[i].len*(q[i].len-1);
        int d=gcd(Ans1[id],Ans2[id]);
        Ans1[id]/=d,Ans2[id]/=d;
    }
    for (re int i=1;i<=m;++i) printf("%lld/%lld\n",Ans1[i],Ans2[i]);
    return 0;
}
最后修改:2019 年 05 月 26 日 03 : 27 PM

发表评论