关于莫队算法

莫队算法，优雅的暴力~

先来一道例题

P3901 数列找不同

引入：如何解决？

1. \(O\)(\(n^2\))

   每次读入询问区间\(l至r\)暴力判定！

2. 如何优化？

   已经知道区间l至r，可以\(O(1)\)扩展至区间l+1至r~

3. 询问无序，如何解决步子过大，复杂过高？？？

   离线询问排序！

4. 如何排序？

   分块思想，以\(sqrt(n)\)为一块，左右端点进行排序

中间：代码模板？

1. 单点添加

  inline void add(int x){//添加x位置的数if(to[x]==1) cnt++;to[x]++;}//to是桶，cnt是计数的

2. 单点删除

  inline void del(int x){//删除x位置的数if(to[x]==2) cnt--;to[x]--;}//与上同理~

3. 询问离线

  struct question{//结构体int lz,rz,id;//记录询问左右端点,询问编号}qu[M];

4. 询问排序

  inline bool cmp(qur a,qur b){return pos[a.lz]==pos[b.lz]?a.rz<b.rz:pos[a.lz]<pos[b.lz];}//

然后你会发现相当于每次移动左右指针，但是移动次数减少的同时，解决的询问也多了。