题解 | 信息学奥赛一本通 - 小Z的袜子

简要题意

给定一个长度为n的序列，每次询问一个区间[l,r]中，随机抽取两个数字，这两个数字相同的概率

既然是静态的，不妨考虑莫队。我们发现这题的性质满足莫队所需的性质，我们只需要考虑状态的转移，即插入一个点和删除一个点即可

考虑一个颜色对答案的贡献，设s[i]表示区间内第i种颜色的数量，很容易推出这一种袜子的贡献为

那么我们记录s，每次插入和删除做相应的操作即可

#include<cstdio>
#include<cmath>
#include<algorithm>

using namespace std;

const int maxn=50005;
long long int c[maxn];
long long int sum[maxn];

struct node{
    long long int l,r,num;
}q[maxn];

struct res{
    long long int a,b;
}anss[maxn];
long long int block;
long long int ans;

bool cmp(node a,node b){
    return (a.r/block)==(b.r/block)?a.l<b.l:a.r<b.r;
}

inline void del(int x){
    ans-=sum[c[x]]*sum[c[x]];
    sum[c[x]]--;
    ans+=sum[c[x]]*sum[c[x]];
}

inline void add(int x){
    ans-=sum[c[x]]*sum[c[x]];
    sum[c[x]]++;
    ans+=sum[c[x]]*sum[c[x]];
}

int main()
{
    long long int n,m;
    scanf("%lld%lld",&n,&m);
    block=sqrt(n);
    for(long long int i=1;i<=n;i++){
        scanf("%lld",&c[i]);
    }
    for(long long int i=1;i<=m;i++){
        scanf("%lld%lld",&q[i].l,&q[i].r);
        q[i].num=i;
    }
    sort(q+1,q+1+m,cmp);
    int l=1,r=0;
    for(long long int i=1;i<=m;i++){
        long long int ql=q[i].l,qr=q[i].r;
        if(ql==qr){
            anss[q[i].num].a=0;
            anss[q[i].num].b=1;
            continue;
        }
        while(l<ql){
            del(l);
            l++;
        }
        while(l>ql){
            add(l-1);
            l--;
        }
        while(r<qr){
            add(r+1);
            r++;
        }
        while(r>qr){
            del(r);
            r--;
        }
        anss[q[i].num].a=ans-q[i].r+q[i].l-1;
        anss[q[i].num].b=(q[i].r-q[i].l+1)*(q[i].r-q[i].l);
        int gcdd=__gcd(anss[q[i].num].a,anss[q[i].num].b);
        anss[q[i].num].a/=gcdd;
        anss[q[i].num].b/=gcdd;
    }
    for(long long int i=1;i<=m;i++){
        printf("%lld/%lld\n",anss[i].a,anss[i].b);
    }
    return 0;
}
/*
6 4
1 2 3 3 3 2
2 6
1 3
3 5
1 6
*/