牛客练习赛68 A-莫队复习

这是精髓

为什么不考虑普通排序呢？好问题。聪明的你应该懂了。

如果优先按照左端点排序。这种排序的方式，保证左端点只会向右挪，但是右端点每次最坏还是可以从最前面挪到最
后面，从最后面挪到最前面，这样的复杂度还是 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的初始化以及加减的位置问题：

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--，那么位置二就会被删除，求出的结果就不正确。对于区间的操作，可以借这道题手模手模数据，很多时候动动手理解会更深

很典型，可以用线段树维护区间最小值，也可以莫队离线查询

莫队解法：
再加入一个位置的数时，我们记录一个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];
}