莫队入门例题：2038: [2009国家集训队]小Z的袜子(hose)

待我称王封你为后i 2022-02-23 05:08 218阅读 0赞

题目大意：

## Description ##

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

## Input ##

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

## Output ##

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

[传送门][Link 1]

本人代码说明：莫队是基于分块思想的，即“**莫队算法巧妙地将询问离线排序，使得其复杂度无比美妙……。莫队的优化基于分块思想：对于两个询问，若在其l在同块，那么将其r作为排序关键字，若l不在同块，就将l作为关键字排序（这就是双关键字）。**”

但是个人感觉不用这么写 直接一个sort根据左右区间升序排序不就得了   还少了一个while降低了复杂度

当然 ：并不是说我这样排序是优化，只是可能我才疏学浅，不明白分块排序的精髓

第一次修改：他妈的，我就是才疏学浅！！！分块排序是有原因的 ，试想   三个区间1-2   1-100000000   2-3，这样还不得跳死。

所以还是使用分块。这个代码就不修改了 ，本文最后有分块排序莫队的模板代码

#include<bits/stdc++.h>
    using namespace std;
    typedef long long ll;
    ll GCD(ll a,ll b){while(b^=a^=b^=a%=b);return a;}//GCD 
    struct Node{int l,r,id;ll A,B;}res[60000];
    int n,m,color[60000];
    ll ans,sum[60000];//sum当前队列中有多少合适颜色 
    bool cmp(Node a,Node b){return a.l==b.l?a.r<b.r:a.l<b.l;}//为了莫队进行的操作 
    bool CMP(Node a,Node b){return a.id<b.id;}//为了输出进行的操作 
    void revise(int x,int add){
    	ans-=sum[color[x]]*sum[color[x]];//减去这个颜色的所有值 
    	sum[color[x]]+=add;//对队列的这个颜色进行修改 
    	ans+=sum[color[x]]*sum[color[x]];//加上这个颜色 
    }
    int main(){
    	scanf("%d%d",&n,&m);
    	int unit=sqrt(n);
    	for(int i=1;i<=n;i++)scanf("%d",&color[i]);
    	for(int i=1;i<=m;i++){
    		scanf("%d%d",&res[i].l,&res[i].r);
    		res[i].id=i;
    	}
    	sort(res+1,res+m+1,cmp);
    	int l=1,r=0;
    	for(int i=1;i<=m;i++){//依次进行遍历 
    		while(l<res[i].l)revise(l,-1),l++;
            while(r<res[i].r)revise(r+1,1),r++;
            while(r>res[i].r)revise(r,-1),r--;
            
    		if(res[i].l==res[i].r){
    			res[i].A=0;
    			res[i].B=1;
    			continue;
    		}
    		res[i].A=ans-(res[i].r-res[i].l+1);
    		res[i].B=1ll*(res[i].r-res[i].l+1)*(res[i].r-res[i].l);
    		ll tt=GCD(res[i].A,res[i].B);
    		res[i].A/=tt;
    		res[i].B/=tt;
    	}	
    	sort(res+1,res+m+1,CMP);
    	for(int i=1;i<=m;i++)printf("%lld/%lld\n",res[i].A,res[i].B); 
    	return 0;
    }

下面是大佬具体解题思路：[传送门][Link 1]

**目前的题型概括为三种：****普通莫队，树形莫队以及带修莫队。**

**若谈及入门，那么[BZOJ2038][]的美妙袜子一题堪称顶尖。**

**【例题一】袜子**

**·述大意：**

**     进行区间询问\[l,r\]，输出该区间内随机抽两次抽到相同颜色袜子的概率。**

**·分析：**

**     首先考虑对于一个长度为n区间内的答案如何求解。题目要求Ans使用最简分数表示：那么分母就是n\*n-n(表示两两袜子之间的随机组合)，分子是一个累加和-n，累加的内容是该区间内每种颜色i出现次数sum\[i\]的平方。**

**     将莫队算法抬上议程。莫队算法的思路是，离线情况下对所有的询问进行一个美妙的SORT()，然后两个指针l,r（本题是两个，其他的题可能会更多）不断以看似暴力的方式在区间内跳来跳去，最终输出答案。**

**     掌握一个思想基础：两个询问之间的状态跳转。如图，当前完成的询问的区间为\[a,b\],下一个询问的区间为\[p,q\],现在保存\[a,b\]区间内的每个颜色出现次数的sum\[\]数组已经准备好，\[a,b\]区间询问的答案Ans1已经准备好，怎样用这些条件求出\[p,q\]区间询问的Ans2？**

[![image][]][image 1]

**考虑指针向左或向右移动一个单位，我们要付出多大的代价才能维护sum\[\]和Ans(即使得sum\[\],Ans保存的是当前\[l,r\]的正确信息)。我们美妙地对图中l,r的向右移动一格进行分析：**

[![image][image 2]][image_image 2]

**如图啦。l指针向右移动一个单位，所造成的后果就是：我们损失了一个绿色方块。那么怎样维护？美妙地，sum\[绿色\]减去1。那Ans如何维护？先看分母，分母从n2变成(n-1)2，分子中的其他颜色对应的部分是不会变的，绿色却从sum\[绿色\]2变成(sum\[绿色\]-1)2 ，为了方便计算我们可以直接向给Ans减去以前该颜色的答案贡献(即sum\[绿色\]2)再加上现在的答案贡献(即(sum\[绿色\]-1)2 )。同理，观赏下面的r指针移动，将是差不多的。**

[![image][image 3]][image_image 3]

**·如图r指针的移动带来的后果是，我们多了一个橙色方块。所以操作和上文相似，只不过是sum\[橙色\]++。**

**·回归正题地，我们美妙的发现，知道一个区间的信息，要求出旁边区间的信息（旁边区间指的是当前区间的一个指针通过加一减一得到的区间），竟只需要O(1)的时间。**

**·就算是这样，到这里为止的话莫队算法依旧无法焕发其光彩，原因是：如果我们以读入的顺序来枚举每个询问，每个询问到下一个询问时都用上述方法维护信息，那么在你脑海中会浮现出l,r跳来跳去的疯狂景象，疯狂之处在于最坏情况下时间复杂度为：O(n2)————如果要这样玩，那不如写一个暴力程序。**

**·“莫队算法巧妙地将询问离线排序，使得其复杂度无比美妙……”在一般做题时我们时常遇到使用排序来优化枚举时间消耗的例子。莫队的优化基于分块思想：对于两个询问，若在其l在同块，那么将其r作为排序关键字，若l不在同块，就将l作为关键字排序（这就是双关键字）。大米饼使用Be\[i\]数组表示i所属的块是谁。排序如：**

**[![image][image 4]][image_image 4]**

**·值得强调的是，我们是在对询问进行操作。**

**·时间复杂度分析（分类讨论思想）：**

**首先，枚举m个答案，就一个m了。设分块大小为unit。**

**分类讨论：**

**①l的移动：若下一个询问与当前询问的l所在的块不同，那么只需要经过最多2\*unit步可以使得l成功到达目标.复杂度为：O(m\*unit)**

**②r的移动：r只有在Be\[l\]相同时才会有序（其余时候还是疯狂地乱跳，你知道，一提到乱跳，那么每一次最坏就要跳n次！），Be\[l\]什么时候相同？在同一块里面l就Be\[\]相同。对于每一个块，排序执行了第二关键字：r。所以这里面的r是单调递增的，所以枚举完一个块，r最多移动n次。总共有n/unit个块:复杂度为：O(n\*n/unit)**

**总结：O(n\*unit+n\*n/unit)（n,m同级，就统一使用n）**

**根据基本不等式得：当unit为sqrt(n)时，得到莫队算法的真正复杂度：**

**O(n\*sqrt(n))**

**·代码上来了（莫队喜欢while）：**

#include<stdio.h>
    #include<algorithm>
    #include<iostream>
    #include<math.h>
    #include<cstring>
    #define go(i,a,b) for(int i=a;i<=b;i++)
    #define mem(a,b) memset(a,b,sizeof(a))
    #define ll long long 
    using namespace std;const int N=50003;
    struct Mo{int l,r,ID;ll A,B;}q[N];ll S(ll x){return x*x;}
    ll GCD(ll a,ll b){while(b^=a^=b^=a%=b);return a;}
    int n,m,col[N],unit,Be[N];ll sum[N],ans;
    bool cmp(Mo a,Mo b){return Be[a.l]==Be[b.l]?a.r<b.r:a.l<b.l;}
    bool CMP(Mo a,Mo b){return a.ID<b.ID;};
    void revise(int x,int add){ans-=S(sum[col[x]]),sum[col[x]]+=add,ans+=S(sum[col[x]]);}
    int main()
    {
        scanf("%d%d",&n,&m);unit=sqrt(n);
        go(i,1,n)scanf("%d",&col[i]),Be[i]=i/unit+1;;
        go(i,1,m)scanf("%d%d",&q[i].l,&q[i].r),q[i].ID=i;
        
        sort(q+1,q+m+1,cmp);
        
        int l=1,r=0;
        go(i,1,m)
        {
            while(l<q[i].l)revise(l,-1),l++;
            while(l>q[i].l)revise(l-1,1),l--;
            while(r<q[i].r)revise(r+1,1),r++;
            while(r>q[i].r)revise(r,-1),r--;
            
            if(q[i].l==q[i].r){q[i].A=0;q[i].B=1;continue;}
            q[i].A=ans-(q[i].r-q[i].l+1);
            q[i].B=1LL*(q[i].r-q[i].l+1)*(q[i].r-q[i].l);
            ll gcd=GCD(q[i].A,q[i].B);q[i].A/=gcd;q[i].B/=gcd;
        }
        
        sort(q+1,q+m+1,CMP);
        go(i,1,m)printf("%lld/%lld\n",q[i].A,q[i].B);
        return 0;
    }//Paul_Guderian

[Link 1]: https://www.lydsy.com/JudgeOnline/problem.php?id=2038
[BZOJ2038]: http://www.lydsy.com/JudgeOnline/problem.php?id=2038
[image]: /images/20220223/7c90c9fc058741b2ad93b8f3c572c1e6.png
[image 1]: http://images2015.cnblogs.com/blog/1101338/201706/1101338-20170602160312649-460614740.png
[image 2]: https://images2015.cnblogs.com/blog/1101338/201706/1101338-20170602160316008-815266085.png
[image_image 2]: /images/20220223/a6760da34c1e4dc1814f2c9792ba3d04.png
[image 3]: https://images2015.cnblogs.com/blog/1101338/201706/1101338-20170602160317836-681652879.png
[image_image 3]: /images/20220223/158da2a86fd147f6b492c26dbd3792b9.png
[image 4]: https://images2015.cnblogs.com/blog/1101338/201706/1101338-20170602160319493-1978752305.png
[image_image 4]: /images/20220223/077844cff93f43c2a395d62767978cfe.png