前言
有时候题解不仅仅是题解关于莫队
- 现在只说普通莫队
- 离线处理区间问题,可以发现某些题的条件是必须由上一个答案转移过来,就是因为出题人害怕被莫队暴虐(fake,反正我都要被虐)
- 他有许多神奇操作:询问的分块排序,以及区间的伸缩
- 莫队的分块排序
这是精髓
为什么不考虑普通排序呢?好问题。聪明的你应该懂了。
如果优先按照左端点排序。这种排序的方式,保证左端点只会向右挪,但是右端点每次最坏还是可以从最前面挪到最
后面,从最后面挪到最前面,这样的复杂度还是 O(nm),是不行的,就像[1,n],[2,3],[3,n],[4,5]...来来回回,何来AC?那么这样不行,就要换种方式。这里引用一下洛谷日报第四十八期的句子:
我们的排序是要使左右端点挪动的次数尽量少,所以这里就有一种排序方法:
将序列分成 sqrt(n)个长度为 sqrt(n) 的块,若左端点在同一个块内,则按右端点排序(以左端点所在块为第一关键字,右端点为第二关键字)注意,莫队的挪动操作要尽量快,若不是 O(1)的,复杂度会原地爆炸对于n与m同阶,一般可以设块长度为 sqrt(n)
- 区间伸缩
其实就是将左右端点的指针移到指定的询问区间
关于L=1,R=0的初始化以及加减的位置问题:
- 先声明,在函数add(L++)里,先进行add(L),然后L才加一,而sub(--L)时,L先减一,再进行sub(L)
- 假设当前询问区间为[1,x],可以肯定的是位置1和位置x肯定包含在内,但是此时L为1,所以L必不会移动,但是位置1还没有被算进去,这时便add(++R),可以保证[1,x]里的每一个数都只被算了一遍而且没有漏下一个。
- 假设当前L=2,R=3,询问区间为[1,3],这个时候肯定要左移L,但是如果不先--L,而是L--,那么位置二就会被删除,求出的结果就不正确。对于区间的操作,可以借这道题手模手模数据,很多时候动动手理解会更深
- 关于这道题
很典型,可以用线段树维护区间最小值,也可以莫队离线查询
莫队解法:
再加入一个位置的数时,我们记录一个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++);
至于原因,因当时过于轻狂,未能记得,还请指点(^▽^)