清橙A1206 小Z的袜子（莫队算法模板）-CSDN博客

本文链接：https://blog.csdn.net/acm_cxq/article/details/51909680

这篇博客介绍了如何利用莫队算法解决区间内不同类别袜子数量平方和的计算问题，强调了莫队算法在静态不修改的区间查询中的应用，并提供了相关理解及代码示例。

摘要生成于 C知道，由 DeepSeek-R1 满血版支持，前往体验 >

A1206. 小Z的袜子

时间限制： 1.0s 内存限制： 512.0MB

总提交次数： 1328 AC次数： 396 平均分： 46.54

将本题分享到：

查看未格式化的试题提交试题讨论

试题来源

　　2010中国国家集训队命题答辩

问题描述

　　作为一个生活散漫的人，小Z每天早上都要耗费很久从一堆五颜六色的袜子中找出一双来穿。终于有一天，小Z再也无法忍受这恼人的找袜子过程，于是他决定听天由命……
　　具体来说，小Z把这N只袜子从1到N编号，然后从编号L到R(L 尽管小Z并不在意两只袜子是不是完整的一双，甚至不在意两只袜子是否一左一右，他却很在意袜子的颜色，毕竟穿两只不同色的袜子会很尴尬。
　　你的任务便是告诉小Z，他有多大的概率抽到两只颜色相同的袜子。当然，小Z希望这个概率尽量高，所以他可能会询问多个(L,R)以方便自己选择。

输入格式

　　输入文件第一行包含两个正整数N和M。N为袜子的数量，M为小Z所提的询问的数量。
　　接下来一行包含N个正整数Ci，其中Ci表示第i只袜子的颜色，相同的颜色用相同的数字表示。
　　再接下来M行，每行两个正整数L，R表示一个询问。

输出格式

　　输出文件包含M行，对于每个询问在一行中输出分数A/B表示从该询问的区间[L,R]中随机抽出两只袜子颜色相同的概率。若该概率为0则输出0/1，否则输出的A/B必须为最简分数。（详见样例）

样例输入

样例输出

样例说明

　　询问1：共C(5,2)=10种可能，其中抽出两个2有1种可能，抽出两个3有3种可能，概率为(1+3)/10=4/10=2/5。
　　询问2：共C(3,2)=3种可能，无法抽到颜色相同的袜子，概率为0/3=0/1。
　　询问3：共C(3,2)=3种可能，均为抽出两个3，概率为3/3=1/1。
　　注：上述C(a, b)表示组合数，组合数C(a, b)等价于在a个不同的物品中选取b个的选取方案数。

数据规模和约定

　　30%的数据中 N,M ≤ 5000；
　　60%的数据中 N,M ≤ 25000；
　　100%的数据中 N,M ≤ 50000，1 ≤ L < R ≤ N，Ci ≤ N。

思路：我们假设区间[L,R]之间所有不同类别袜子的数量分别为a,b,c...x

那么ans=(a*(a-1)/2+b*(b-1)/2+c*(c-1)/2...+x*(x-1)/2)/((R-L+1)*(R-L)/2)=(a²+b²+c²+...x²-(a+b+c+...x))/((R-L+1)*(R-L))=(a²+b²+c²+...x²-(R-L+1))/((R-L+1)*(R-L))

那么关键就在于如何求解区间内所有不同类别的袜子的数量的平方之和

这里就要用到莫队算法了，具体可以看这位大神的博客，写得很详细。

点击打开链接

这里讲一点自己的理解，所谓的莫队算法其实就是解决静态不修改的区间查询问题。不过这一类问题必须满足在知道[L,R]的情况下，可以递推出[L,R+1],[L,R-1],[L-1,R],,[L-1,R+1],[L-1,R-1],[L+1,R-1],[L+1,R],[L+1,R+1]等等。然后把所有的询问都保存下来，从小到大地去递推（其实感觉有点像取尺法？）

对应于不同的题型，只要修改update函数即可。

代码：

#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <cmath>
using namespace std;
#define N 50050
int a[N],p[N];
long long ansl[N],ansr[N];
long long ans;
long long num[N];
struct Node
{
    int l,r,id;
}q[N];
long long gcd(long long a,long long b)
{
    return b?gcd(b,a%b):a;
}
bool cmp(Node a,Node b)
{
    if(p[a.l]==p[b.l]) return a.r<b.r;
    return p[a.l]<p[b.l];
}
void update(int j,int v)
{
    ans-=num[a[j]]*num[a[j]];
    num[a[j]]+=v;
    ans+=num[a[j]]*num[a[j]];
}
int main()
{
    int n,m;
    int l,r;
    while(~scanf("%d %d",&n,&m))
    {
        memset(num,0,sizeof(num));
        int bk=ceil(sqrt(1.0*n));
        for(int i=1;i<=n;i++)
        {
            scanf("%d",&a[i]);
            p[i]=(i-1)/bk;
        }
        for(int i=0;i<m;i++)
        {
            scanf("%d %d",&q[i].l,&q[i].r);
            q[i].id=i;
        }
        sort(q,q+m,cmp);
        int pl=1,pr=0;
        ans=0;
        for(int i=0;i<m;i++)
        {
            int id=q[i].id;
            if(q[i].l==q[i].r)
            {
                ansl[id]=0,ansr[id]=1;
                continue;
            }
            if(pr<q[i].r)
            {
                for(int j=pr+1;j<=q[i].r;j++)
                    update(j,1);
            }
            else
            {
                for(int j=pr;j>q[i].r;j--)
                    update(j,-1);
            }
            pr=q[i].r;
            if(pl<q[i].l)
            {
                for(int j=pl;j<q[i].l;j++)
                    update(j,-1);
            }
            else
            {
                for(int j=pl-1;j>=q[i].l;j--)
                    update(j,1);
            }
            pl=q[i].l;
            ansl[id]=ans-q[i].r+q[i].l-1;
            ansr[id]=(long long)(q[i].r-q[i].l+1)*(q[i].r-q[i].l);
            long long cc=gcd(ansl[id],ansr[id]);
            ansl[id]/=cc,ansr[id]/=cc;
        }
        for(int i=0;i<m;i++)
            printf("%lld/%lld\n",ansl[i],ansr[i]);
    }
    return 0;
}