莫队初探（不带修/例题极少）By cellur925

因为今天考到莫队裸题了嘤嘤嘤...而我这样的蒟蒻肯定不会这样的高端算法啊QAQ。于是暴力水了40分qwq。

正如上文所说，我实在太菜了，于是学习莫队也只是学习了最简单的不带修普通莫队，如果我能苟到省选那就再继续学啦。

掏心推荐：深度好文，浅谈根号算法--分块 By new2zy

一、莫队的思想及处理的问题

红太阳金涛说的吼啊：莫队本质上就是一种优化的暴力。

所以莫队到底能适用什么样的问题呢？基本上所有的离线区间查询问题（暂时不带修）都能用莫队算法苟过233...所以莫队算法还真是强啊%%。

离线区间查询？意思就是在说，我们先把所有需要进行区间查询的信息保存下来，然后根据一定的方法规则对这些区间查询信息进行排序。（这里我们一会再说qwq）

排序之后，我们就可以用两个指针$posl$和$posr$（可能有些像cf上的two pointer？不太确定qwq），不断调整他们的位置直到与查询区间精确重合并维护$[posl,posr]$区间内的信息，来处理询问。

而莫队算法也是需要把序列分成很多块的（分块算法的好基友），一般是分成$sqrt(n)$块，当然也有其他玄学分块方式。

而莫队的时间复杂度一般是$O(n*sqrt(n))$的，具体分析过程我就光速逃了qwq。（不会qwq）

另外，刚才我们留了个锅，就是关于将询问排序的方法：

一般的排序是这样的：先按左端点所在块排，再按右端点位置排。但是这个排序有时比较弱，卡不过毒瘤们的精心构造。
于是产生了更加优秀的一种排序：按奇偶块排序。这也是比较通用的。如果区间左端点所在块不同，那么就直接按左端点从小到大排；如果相同，鸡块奇块按右端点从小到大排，偶块按右端点从大到小排。

bool cmp(query a,query b)

{

    return (a.l/block)^(b.l/block) ? a.l<b.l : (((a.l/block)&) ? a.r<b.r : a.r>b.r);

}

至于证明...我太菜了放过我吧

二、丢几道例题跑

其实..莫队的核心代码除排序的cmp外只有四行...

        int l=ask[i].l,r=ask[i].r;

        while(posl<l) remove(posl++);  //当前区间左端点在查询区间的左边 想要向右移 但是因为当前的posl不在查询区间中所以把它对答案的贡献去除。

        while(posr>r) remove(posr--);  //其他同理233

        while(posl>l) add(--posl);

        while(posr<r) add(++posr);

        ans[ask[i].id]=noww;

什么这不是六行嘛

例题1 小B的询问

莫队裸题。左右指针移动实际上就是数字的增减，我们改变了桶的大小（计数数组大小后），考虑如果一个数字p减小，那么它对答案的贡献就会少。少了多少呢？考虑完全平方公式。设$x=cnt[p]$。

$(x+1)^2$------->>>>>>$x^2$

$x^2+2*x+1$------->>>>>>$x^2$

显然少了$2*x+1$，那么增加同理。之后就是套裸的莫队了。

#include<cstdio>

#include<algorithm>

#include<cmath>

using namespace std;

int n,m,k,block,posl=,posr,noww;

int seq[],ans[],sum[];

struct query{

    int l,r,id,in;

}ask[];

bool cmp(query a,query b)

{

    return (a.l/block)^(b.l/block) ? a.l<b.l : (((a.l/block)&) ? a.r<b.r : a.r>b.r);

}

void remove(int x)

{

    sum[seq[x]]--;

    noww-=*sum[seq[x]]+;

}

void add(int x)

{

    sum[seq[x]]++;

    noww+=*sum[seq[x]]-;

}

int main()

{

    scanf("%d%d%d",&n,&m,&k);

    block=sqrt(n);

    for(int i=;i<=n;i++) scanf("%d",&seq[i]);

    for(int i=;i<=m;i++)

    {

        scanf("%d%d",&ask[i].l,&ask[i].r);

        ask[i].id=i;

        ask[i].in=ask[i].l/block;

    }

    sort(ask+,ask++m,cmp);

    for(int i=;i<=m;i++)

    {

        int l=ask[i].l,r=ask[i].r;

        while(posl<l) remove(posl++);

        while(posr>r) remove(posr--);

        while(posl>l) add(--posl);

        while(posr<r) add(++posr);

        ans[ask[i].id]=noww;

    }

    for(int i=;i<=m;i++) printf("%d\n",ans[i]);

    return ;

}

例题2

也是一道裸的不带修莫队。因为每个数范围在1e9内，所以先离散化一下，然后上裸的莫队。但是正睿神机（？）竟然卡unique......嘤。

#include<cstdio>

#include<algorithm>

#include<cmath>

using namespace std;

int n,Q,block,m,posl=,posr,noww;

int seq[],b[],tong[],ans[];

struct query{

    int l,r,id,in;

}ask[];

void re(int &x)

{

    x=;

    char ch=getchar();

    bool flag=false;

    while(ch<''||ch>'') flag|=(ch=='-'),ch=getchar();

    while(ch>=''&&ch<='') x=(x<<)+(x<<)+(ch^),ch=getchar();

    x=flag ? -x : x;

}

bool cmp(query a,query b)

{

//    return (a.l/block)^(b.l/block) ? a.l<b.l : (((a.l/block)&1) ? a.r<b.r : a.r>b.r);

    return a.in==b.in?(a.in&)?a.r<b.r:a.r>b.r:a.in<b.in;

}

void remove(int x)

{

    tong[seq[x]]--;

    if(tong[seq[x]]==) noww++;

    if(tong[seq[x]]==) noww--;

}

void add(int x)

{

    tong[seq[x]]++;

    if(tong[seq[x]]==) noww++;

    if(tong[seq[x]]==) noww--;

}

int main()

{

    re(n);re(Q);

    for(int i=;i<=n;i++) re(seq[i]),b[i]=seq[i];

    sort(b+,b++n);

//    m=unique(b+1,b+1+n)-(b+1);

    for(int i=;i<=m;i++) seq[i]=lower_bound(b+,b++m,seq[i])-b;

    block=sqrt(n);

    for(int i=;i<=Q;i++)

    {

        re(ask[i].l);re(ask[i].r);

        ask[i].id=i;ask[i].in=ask[i].l/block;

    }

    sort(ask+,ask++Q,cmp);

    for(int i=;i<=Q;i++)

    {

        int l=ask[i].l,r=ask[i].r;

        while(posl<l) remove(posl++);

        while(posr>r) remove(posr--);

        while(posl>l) add(--posl);

        while(posr<r) add(++posr);

        ans[ask[i].id]=noww;

    }

    for(int i=;i<=Q;i++) printf("%d\n",ans[i]);

    return ;

}

更强的莫队算法，以后再见啦：）（如果我联赛后还能继续苟233）

巴特西

莫队初探（不带修/例题极少）By cellur925

一、莫队的思想及处理的问题

二、丢几道例题跑

最新文章

热门文章