• 前言

    有时候题解不仅仅是题解
  • 关于莫队

  1. 现在只说普通莫队
  2. 离线处理区间问题,可以发现某些题的条件是必须由上一个答案转移过来,就是因为出题人害怕被莫队暴虐(fake,反正我都要被虐)
  3. 他有许多神奇操作:询问的分块排序,以及区间的伸缩
  • 莫队的分块排序
  1. 这是精髓

  2. 为什么不考虑普通排序呢?好问题。聪明的你应该懂了。
    图片说明
    如果优先按照左端点排序。这种排序的方式,保证左端点只会向右挪,但是右端点每次最坏还是可以从最前面挪到最
    后面,从最后面挪到最前面,这样的复杂度还是 O(nm),是不行的,就像[1,n],[2,3],[3,n],[4,5]...来来回回,何来AC?

  3. 那么这样不行,就要换种方式。这里引用一下洛谷日报第四十八期的句子:

    我们的排序是要使左右端点挪动的次数尽量少,所以这里就有一种排序方法:
    将序列分成 sqrt(n)个长度为 sqrt(n) 的块,若左端点在同一个块内,则按右端点排序(以左端点所在块为第一关键字,右端点为第二关键字)注意,莫队的挪动操作要尽量快,若不是 O(1)的,复杂度会原地爆炸对于n与m同阶,一般可以设块长度为 sqrt(n)

  • 区间伸缩
    图片说明
  1. 其实就是将左右端点的指针移到指定的询问区间

  2. 关于L=1,R=0的初始化以及加减的位置问题:

    1. 先声明,在函数add(L++)里,先进行add(L),然后L才加一,而sub(--L)时,L先减一,再进行sub(L)
    2. 假设当前询问区间为[1,x],可以肯定的是位置1和位置x肯定包含在内,但是此时L为1,所以L必不会移动,但是位置1还没有被算进去,这时便add(++R),可以保证[1,x]里的每一个数都只被算了一遍而且没有漏下一个。
    3. 假设当前L=2,R=3,询问区间为[1,3],这个时候肯定要左移L,但是如果不先--L,而是L--,那么位置二就会被删除,求出的结果就不正确。对于区间的操作,可以借这道题手模手模数据,很多时候动动手理解会更深
  • 关于这道题
  1. 很典型,可以用线段树维护区间最小值,也可以莫队离线查询

  2. 莫队解法:
    再加入一个位置的数时,我们记录一个cnt数组,表示某一个数的出现次数,如果是当前的最小没出现过的数出现了,那么只能向大的去找

    inline void add(int x)
    {
     cnt[a[x]]++;
     if(cnt[a[x]]==1&&a[x]==tmd&&va)
     {
         int op=a[x];
         while(++op)
             if(!cnt[op])
             {
                 tmd=op;
                 return ;
             }
     }
    }

    删除时,直接取最小就好了

    inline void del(int x)
    {
     cnt[a[x]]--;
     if(cnt[a[x]]==0&&a[x]<=tmd&&va) tmd=a[x];
    }
  • 后话
    代码我就不放了,因为有些地方为了卡时加了奇怪的操作(好像是错的,但是过了),而且区间伸缩时不太规范。我的学长告诉我,最好先加再减,即
    while(l>s[i].l) add(--l);
    while(r<s[i].r) add(++r);
    while(r>s[i].r) del(r--);
    while(l<s[i].l) del(l++);
    至于原因,因当时过于轻狂,未能记得,还请指点(^▽^)