您的位置: 首页  >  文章  >  浅谈莫队

浅谈莫队

分类: 文章 • 2024-07-04 09:09:04

距NOIP2018 5天，本蒟蒻发布了第一篇博文

花了一下午的时间学莫队，现在才终于弄清了一二（真的是太菜了），至于理由嘛，大佬们分析得太透彻了，从均值不等式到曼哈顿最小生成树，带着菜鸡我腾云驾雾.......一脸懵逼

事实上，莫队本没有原来想象的那么高级，换言之，它是一种老少皆宜的优美暴力

避免内容的冗杂降低可读性，我们就免去寒暄进入正题

·排序巧妙优化复杂度，带来NOIP前的最后一丝宁静。几个活蹦乱跳的指针的跳跃次数，决定着莫队算法的优劣……

要理解上述的真谛，我们先看一道题：

题目描述

现有数列A1,A2,A3,A4,A5....An，Q 个询问(L_i,R_i)，AL->AR 是否互不相同

输入输出格式

输入格式：

第1 行，2 个整数N,QN,Q

第2 行，N 个整数A1,A2,A3.....

Q 行，每行2 个整数L,R​

 

输出格式：

对每个询问输出一行，“Yes” 或者“No”

 

输入输出样例

输入样例#1： 
 
4 2
1 2 3 2
1 3
2 4
输出样例#1： 
 
Yes
No

说明

• 对于50% 的数据，N,Q \le 10^3N,Q≤103

• 对于100% 的数据，1 \le N,Q \le 10^5, 1 \le A_i \le N, 1 \le L_i \le R_i \le N1≤N,Q≤105,1≤Ai​≤N,1≤Li​≤Ri​≤N

原题传送门

·找不同，简单嘛，我们拿一个数组，桶排的思想，不同的数放不同的桶最后for一遍，看每一个桶是不是为1就行了

自然，楼上的T飞了

暴力就这么不堪一击的吗？

您的莫队已上线

浅谈莫队

相比于普通的暴力，莫队应用了DP的思想，如图所示，当我们询问了a-b要询问p-q之时，我们可以轻易地发现p-b区间其实是可以再次利用的

所以呢，我们要做的，便是移动a至p，b至q，减去a-p里不再使用的，加上b-q里新需求的再直接使用已经处理好的p-b便得到了p-q区间里的值

但就算是这样，莫队算法依旧无法焕发其光彩，原因是：如果我们以读入的顺序来枚举每个询问，每个询问到下一个询问时都用上述方法维护信息，那么在一些精心制造的数据下

其最坏情时间复杂度为：O(n2)

举个栗子，有6个询问如下：(1, 100), (2, 2), (3, 99), (4, 4), (5, 102), (6, 7)。

这个数据已经按照左端点排序了。用上述方法处理时，左端点会移动6次，右端点会移动移动98+97+95+98+95=483次。

其实我们稍微改变一下询问处理的顺序就能做得更好：(2, 2), (4, 4), (6, 7), (5, 102), (3, 99), (1, 100)。

左端点移动次数为2+2+1+2+2=9次，比原来稍多。右端点移动次数为2+3+95+3+1=104，右端点的移动次数大大降低了。

上面的过程启发我们：我们不应该严格按照升序排序，而是根据需要灵活一点的排序方法才能让暴力更为优美

至于排序，就要提到：分块

我们把所有的元素分成多个块（即分块）。分了块跑的会更快。再按照右端点从小到大，左端点块编号相同按右端点从小到大。这样会将效率大大提高

一般而言，块的大小为序列长度/sqrt（询问次数/6）我也不知道为啥要这样，据说要快10%


最后上例题代码

#include <bits/stdc++.h>
using namespace std;
const int N=1e5;
int n,q,lim;
int cnt[N+5],a[N+5];//cnt为记录不同数出现次数的桶 
struct tt
{
    int l,r,id;
}query[N+5];
bool keep[N+5];
bool comp(const tt &a,const tt &b) {return a.l/lim==b.l/lim ? a.r<b.r : a.l<b.l;}
int main()
{
    scanf("%d%d",&n,&q); 
    lim=n/sqrt((m>>1)/3);//分块大小 
    for ( int i=1;i<=n;i++) scanf("%d",&a[i]);
    for ( int i=1;i<=q;i++) scanf("%d%d",&query[i].l,&query[i].r),query[i].id=i;
    sort(query+1,query+1+q,comp);//按规则排序 
    int curl=1,curr=0,ans=0,l,r; 
    for (RE int i=1;i<=q;i++)
    {
        l=query[i].l,r=query[i].r;
        while (curl<l) cnt[a[curl]]--,ans-=(cnt[a[curl++]]==1);//只出现一次 
        while (curl>l) cnt[a[--curl]]++,ans+=(cnt[a[curl]]==2);//出现两次 
        while (curr<r) cnt[a[++curr]]++,ans+=(cnt[a[curr]]==2);
        while (curr>r) cnt[a[curr]]--,ans-=(cnt[a[curr--]]==1);
        if (!ans) keep[query[i].id]=1;
    }
    for (RE int i=1;i<=q;i++) printf(keep[i] ? "Yes\n":"No\n");
    return 0;
}

推荐例题：

1.小Z的袜子

2.数颜色

3.啦啦队排练

 

相关推荐