【洛谷1494】[國家集訓隊] 小Z的襪子（莫隊）

點此看題面

大緻題意： 有\(N\)隻從\(1\sim N\)編号的襪子，告訴你每隻襪子的顔色，\(M\)組詢問，每組詢問給你一個區間\([L\sim R]\)，讓你求出小Z随機抽出\(2\)隻襪子時有多大機率抽到兩隻顔色相同的襪子。

題意轉換

假設這些襪子中共有\(K\)種顔色，則對于第\(i\)種顔色的襪子，抽到兩次的機率為：

\[\frac{cnt[i]*(cnt[i]-1)}{(R-L+1)*(R-L)}

\]

那麼，在整個區間中抽到兩隻相同顔色的襪子的機率就是：

\[\sum_{i=1}^K\frac{cnt[i]*(cnt[i]-1)}{(R-L+1)*(R-L)}

即：

\[\frac{\sum_{i=1}^Kcnt[i]*(cnt[i]-1)}{(R-L+1)*(R-L)}

莫隊

代碼

#include<bits/stdc++.h>
#define LL long long
#define N 50000
#define M 50000
using namespace std;
LL n,Q,a[N+5],pos[N+5],ans1[M+5],ans2[M+5],cnt[N+5];
struct Query
{
    LL l,r,pos;
}q[M+5];
inline char tc()
{
    static char ff[100000],*A=ff,*B=ff;
    return A==B&&(B=(A=ff)+fread(ff,1,100000,stdin),A==B)?EOF:*A++;
}
inline void read(LL &x)
{
    x=0;char ch;
    while(!isdigit(ch=tc()));
    while(x=(x<<3)+(x<<1)+ch-'0',isdigit(ch=tc()));
}
inline void write(LL x)
{
    if(x<0) putchar('-'),x=-x;
    if(x>9) write(x/10);
    putchar(x%10+'0');
}
inline bool cmp(Query x,Query y)
{
    return pos[x.l]<pos[y.l]||(pos[x.l]==pos[y.l]&&(pos[x.l]&1?x.r<y.r:x.r>y.r));
}
inline LL gcd(LL x,LL y)//求最大公因數，為之後的約分做準備
{
    return y?gcd(y,x%y):x;
}
int main()
{
    register LL i;
    for(read(n),read(Q),i=1;i<=n;++i) read(a[i]),pos[i]=(i-1)/sqrt(n)+1;
    for(i=1;i<=Q;++i) read(q[i].l),read(q[i].r),q[i].pos=i;
    sort(q+1,q+Q+1,cmp);
    LL ans=0,L=q[1].l,R=q[1].r;
    for(i=L;i<=R;++i)//先暴力求解第一個問題的答案
    {
        if(++cnt[a[i]]) ans-=((cnt[a[i]]-1)*(cnt[a[i]]-2));
        ans+=cnt[a[i]]*(cnt[a[i]]-1);
    }
    LL t1=ans,t2=(q[1].r-q[1].l+1)*(q[1].r-q[1].l),g=gcd(t1,t2);
    ans1[q[1].pos]=t1/g,ans2[q[1].pos]=t2/g;
    for(i=2;i<=Q;++i)
    {
        if(q[i].l==q[i].r)//題目中的附加說明，對于L=R的情況直接輸出0/1
        {
            ans1[q[i].pos]=0,ans2[q[i].pos]=1;
            continue;
        }
        while(L<q[i].l) ans-=cnt[a[L]]*(cnt[a[L]]-1),--cnt[a[L]],ans+=cnt[a[L]]*(cnt[a[L]]-1),++L;//若L指針小于目前詢問的l，就先更新ans，再移動指針
        while(L>q[i].l) --L,ans-=cnt[a[L]]*(cnt[a[L]]-1),++cnt[a[L]],ans+=cnt[a[L]]*(cnt[a[L]]-1);//若L指針大于目前詢問的l，則操作順序與上面的操作恰好相反
        while(R>q[i].r) ans-=cnt[a[R]]*(cnt[a[R]]-1),--cnt[a[R]],ans+=cnt[a[R]]*(cnt[a[R]]-1),--R;//R指針的操作與L指針類似
        while(R<q[i].r) ++R,ans-=cnt[a[R]]*(cnt[a[R]]-1),++cnt[a[R]],ans+=cnt[a[R]]*(cnt[a[R]]-1);
        LL t1=ans,t2=(q[i].r-q[i].l+1)*(q[i].r-q[i].l),g=gcd(t1,t2);//注意約分
        ans1[q[i].pos]=t1/g,ans2[q[i].pos]=t2/g;
    }
    for(i=1;i<=Q;++i) write(ans1[i]),putchar('/'),write(ans1[i]?ans2[i]:1),putchar('\n');
    return 0;
}
           

敗得義無反顧，弱得一無是處