莫队算法学习笔记(二)——带修莫队[通俗易懂]

莫队算法学习笔记(二)——带修莫队[通俗易懂]前言:什么是莫队莫队算法,是一个十分优雅的暴力。普通的莫队可以轻松解决一些离线问题,但是,当遇上了一些有修改操作的问题,普通莫队就无能为力了。于是,改进后的莫队——带修莫队就这样产生了。Link普通莫队详见博客莫队算法学习笔记(一)——普通莫队接下来,我们一起在普通莫队的基础之上,学会带修莫队这个强大无比的算法。第一个问题:如何处理修改既然是...

前言:什么是莫队

莫队算法,是一个十分优雅暴力

普通的莫队可以轻松解决一些离线问题,但是,当遇上了一些有修改操作的问题,普通莫队就无能为力了。

于是,改进后的莫队——带修莫队就这样产生了。

L i n k Link Link

普通莫队详见博客莫队算法学习笔记(一)——普通莫队

接下来,我们一起在普通莫队的基础之上,学会带修莫队这个强大无比的算法。


第一个问题:如何处理修改

既然是带修莫队,那么第一个关键问题就是如何处理修改

其实,我们可以增加一个变量,来记录对于每一个询问操作,在进行询问之前一共进行了多少次修改,然后对于每一次询问,只要像普通莫队的 L L L指针和 R R R指针一样新增一个 K K K指针来表示当前进行了多少次修改,而 K K K指针的移动也与 L L L指针和 R R R指针是类似的。

模板如下:

register int L=0,R=0,K=0,ans=0;
for(sort(q+1,q+q_num+1,cmp),i=1;i<=q_num;++i)
{ 
   
        while(K<q[i].k) Change(++K);
        while(K>q[i].k) Change(K--);
        while(R<q[i].r) Add(++R);
        while(L>q[i].l) Add(--L);
        while(R>q[i].r) Del(R--);
        while(L<q[i].l) Del(L++);
        res[q[i].pos]=ans;
}
只听到从架构师办公室传来架构君的声音:
棠梨叶落胭脂色,荞麦花开白雪香。有谁来对上联或下联?

C h a n g e ( ) Change() Change()函数、 A d d ( ) Add() Add()函数和 D e l ( ) Del() Del()函数里面的内容自己视题意而定。


第二个问题:如何写排序函数

现在加上了一个 k k k变量来表示在每个询问之前进行了几次操作。

那么,现在的排序函数 c m p ( ) cmp() cmp()应该怎么写呢?

首先,应该判断 l l l是否在同一块内,如果相同,就返回 p o s [ x . l ] &lt; p o s [ y . l ] pos[x.l]&lt;pos[y.l] pos[x.l]<pos[y.l]

然后,应该判断 r r r是否在同一块内,如果相同,就返回 p o s [ x . r ] &lt; p o s [ y . r ] pos[x.r]&lt;pos[y.r] pos[x.r]<pos[y.r]

最后,再比较 k k k的大小,即返回 x . k &lt; y . k x.k&lt;y.k x.k<y.k

模板如下:

此代码由Java架构师必看网-架构君整理
inline bool cmp(Query x,Query y) { if(pos[x.l]^pos[y.l]) return pos[x.l]<pos[y.l];//判断l是否在同一块内,如果相同,就返回pos[x.l]<pos[y.l] if(pos[x.r]^pos[y.r]) return pos[x.r]<pos[y.r];//判断r是否在同一块内,如果相同,就返回pos[x.r]<pos[y.r] return x.k<y.k;//比较k的大小,即返回x.k<y.k }

第三个问题:块的大小

学过莫队的人应该都知道,莫队算法需要分块。

那么带修莫队块的大小应该是多少呢?

我们就需要对这个算法的时间复杂度进行一波分析。

首先我们假设块的大小为 n x n^x nx(其中$0<x< 1 ) , 并 假 设 1),并假设 1m 的 大 小 与 的大小与 n$差不多。

那么我们分别考虑3个指针的移动:

  • 对于 L L L指针

    • 在块内移动时,每一次移动的复杂度应为 O ( n x ) O(n^x) O(nx),由于共有 m m m次询问,因此总复杂度为 O ( n x + 1 ) O(n^{x+1}) O(nx+1)
    • 到下一个块时,每一次移动的复杂度应为 O ( n x ) O(n^x) O(nx),由于块的大小为 O ( n x ) O(n^x) O(nx),因此总块数为 O ( n n x ) O(\frac n{n^x}) O(nxn),因此总复杂度为 O ( n ) O(n) O(n)

    ∴ L ∴L L指针的总复杂度为 O ( n x + 1 ) O(n^{x+1}) O(nx+1)

  • 对于 R R R指针

    • L L L R R R全都在块内移动时,每一次移动的复杂度应为 O ( n x ) O(n^x) O(nx),由于这样的情况共有 O ( ( n n x ) 2 ) O((\frac n{n^x})^2) O((nxn)2),即 O ( n 2 − 2 x ) O(n^{2-2x}) O(n22x)次,因此总复杂度为 O ( n 2 − x ) O(n^{2-x}) O(n2x)
    • L L L块相同且 R R R到下一块时,每一次移动的复杂度应为 O ( n x ) O(n^x) O(nx),由于总块数为 O ( n n x ) O(\frac n{n^x}) O(nxn),即 O ( n 1 − x ) O(n^{1-x}) O(n1x),因此总复杂度为 O ( n 2 − x ) O(n^{2-x}) O(n2x)
    • L L L指针移动到下一个块时,每一次移动的复杂度应为 O ( n ) O(n) O(n),由于这样的情况共有 O ( n n x ) O(\frac n{n^x}) O(nxn),即 O ( n 1 − x ) O(n^{1-x}) O(n1x)次,因此总复杂度为 O ( n 2 − x ) O(n^{2-x}) O(n2x)

    ∴ R ∴R R指针的总复杂度为 O ( n 2 − x ) O(n^{2-x}) O(n2x)

  • 对于 K K K指针

    • L L L R R R全都在块内移动时,此时 K K K指针应该是递增的(因为排序时对于这样的情况我们 r e t u r n return return x . k &lt; y . k x.k&lt;y.k x.k<y.k),所以总复杂度为 O ( n ) O(n) O(n)
    • L L L块相同且 R R R到下一块时,每一次移动的复杂度应为 O ( n ) O(n) O(n),由于这样的情况有 O ( n 2 − 2 x ) O(n^{2-2x}) O(n22x)次,因此总复杂度为 O ( n 3 − 2 x ) O(n^{3-2x}) O(n32x)
    • L L L指针移动到下一个块时,每一次移动的复杂度应为 O ( n ) O(n) O(n),由于这样的情况共有 O ( n 1 − x ) O(n^{1-x}) O(n1x)次,因此总复杂度为 O ( n 2 − x ) O(n^{2-x}) O(n2x)

    ∴ K ∴K K指针的总复杂度为 O ( n m a x ( 2 − x , 3 − 2 x ) ) O(n^{max(2-x,3-2x)}) O(nmax(2x,32x))

综上所述,算法的总时间复杂度应为 O ( n m a x ( x + 1 , 2 − x , 3 − 2 x ) ) O(n^{max(x+1,2-x,3-2x)}) O(nmax(x+1,2x,32x)),那么我们的目的就是找到一个 x x x 0 &lt; x &lt; 1 0&lt;x&lt;1 0<x<1)使 m a x ( x + 1 , 2 − x , 3 − 2 x ) max(x+1,2-x,3-2x) max(x+1,2x,32x)最小。

此时的 x x x应取 2 3 \frac23 32,所以块的大小就是 O ( n 2 3 ) O(n^{\frac23}) O(n32)


第四个问题:时间复杂度

呃,我想这个问题应该已经在上个问题中解决了。

带修莫队的时间复杂度应为 O ( n 5 3 ) O(n^{\frac53}) O(n35)


例题

带修莫队这样差不多就讲完了,下面给一道例题:

【BZOJ2120】数颜色(带修莫队)

L i n k Link Link

【BZOJ2120】数颜色 的题解详见博客【BZOJ2120】数颜色(带修莫队)

架构君码字不易,如需转载,请注明出处:https://javajgs.com/archives/153049
0
   

发表评论