莫队算法（2）
本节主要针对普通的莫队算法给出一些应用
对于给定的数列$\{a_n\}$，有$q$次询问，每次询问区间$[l,r]$中不同的数的个数
$1\le n,q \le 10^5$
这是一道莫队的模板题，也是上一节用到的例题。通过离线算法主要有$n\sqrt n$的莫队和$n\log n$的树状数组两种做法，在线查询的话可以用$n\log n$的主席树维护。
此处笔者想要强调的是莫队算法中排序时的一种普遍的优化——分奇偶排序。一般情况下，奇偶优化能够使得程序运行时间缩短至未优化时的一半。
struct QQ
{
int l,r,id;
bool operator <(const QQ& tmp) const{
if(l/BLOCK==tmp.l/BLOCK){ //奇偶块的右端点升降交替排序
if((l/BLOCK)%2==0) return r<tmp.r; //偶数块升序
else return r>tmp.r; //奇数块降序
}
return l<tmp.l;
}
}q[maxn];对于给定的字符串$s$，有$q$次询问，每次询问区间$s_l \cdots s_r$组成的字符串中有多少个字串经过重排后可以组成一个回文串
示例：
输入
zzqzzq
1 6
2 4
1 1
输出
16
4
1
先剖析问题的本质，字符串重排后能够组成回文串，也就是说，
- 对于字符串长度为偶数时，每个字母出现的次数都为偶数次
- 对于字符串长度为奇数时，最多只有一个字母，出现的字符串长度为奇数次
问题就转换为，询问一个字符串中有多少个字串，其最多只有一个字母数出现的次数为奇数。
我们就有一个比较显然的策略就是，对于每个查询区间，我们暴力遍历它的每一个字串，然后判断该字串有多少个字母出现次数小于等于1。于是我们就得到了一个$O(n^3)$的算法。
显然我们可以通过按照莫队算法的方式对询问进行离线组织，这样的话还是按照上述的暴力更新每次移动左右端点时答案的变化，我们可以得到一个$O(n^2\sqrt n)$的算法。这还是不够。
事实上，我们统计的是每种字母出现的次数，而我们只关心每种字母出现次数的奇偶性，而且字母种类只有26种，那么我们是否可以根据这两点进行优化呢？
答案是肯定的。
根据上面的分析，我们只想要这个串的部分信息，那么每一个任意长度的字符串都是可以通过一个26位的二进制串来表示的，二进制串的第$i$位就表示原字符串中字母$a+i$出现次数的奇偶性。
进一步的分析发现，对于题目给出的原串$s$我们自需要求出它所有前缀的二进制表示$pre_i$就能得到原串所有子串的二进制表示（对于任意个子串$s_l \cdots s_r$，它的二进制表示为 $pre_r \bigoplus pre_{l-1} $ ）
分析到此，我们就可以考虑如何让快速的从$[l,r]$更新到$[l,r+1]$了。每次增加一个右端点进来，就去查看对于该右端点，区间内有多少个左端点与之组合能够对答案产生贡献。这个过程只需要枚举所有能够产生贡献的那27种最终状态（$0 \bigcup 2^i,0 \le i\le 26$）反向计算，那些左端点的$pre_i$应该满足什么样的条件。就能快速得到答案。
问题的时间复杂度为$O(26n\sqrt n)$。
时间复杂度再分析
对于莫队算法，主要需要考虑两个问题
- 一是移动左右端点的时候，相关信息的维护，一般要求是在$O(1)$，有时$O(\log n)$也可以
- 二是当左右端点确定后如何统计答案，这一步的时间复杂度需要做到$O(\sqrt n)$或者$O(\sqrt n \log n)$
CF940F Machine Learning的简化版（原题要求单点修改）
给你一个数组$\{a_n\}$，每次询问区间$[l,r]$每个数字出现次数的$mex$
$mex$指的是一些数字中最小的未出现的自然数。值得注意的是，区间$[l,r]$总有数字是没有出现过的，所以答案不可能为0。
例如：对于数列$\{100,23,5,7,7,7\}$，其中有无穷多个数出现了$0$次，有三个数出现了$1$次，有一个数出现了$3$次。所以这个数列每个数出现次数的$mex$是$2$（没有哪一个数出现了$2$次，其$2$是最小的）
最直接的想法就是暴力统计每个查询区间的数出现了多少次，然后依次扫描寻找没有任何数字出现了$ans$次。
单次统计区间信息需要$O(n)$，可以确定的是答案一定不会超过$\sqrt n$，即每次扫描的时间复杂度为$O(\sqrt n)$。故总的时间复杂度为$O(n^2)$。
利用莫队算法，每次移动左右端点的时间复杂度为$O(1)$，需要移动$O(n\sqrt n)$次端点。每次询问答案的时间复杂度为$O(\sqrt n)$，共需要询问$O(n)$次答案。故莫队算法总的的时间复杂度为$O(n\sqrt n)$。
给定一个长度为$n$的序列$\{a_n\}$，$m$次询问，每次询问给定一个区间$[l,r]$，如果这个区间里存在只出现一次的数，输出这个数（如果有多个就输出任意一个），没有就输出$0$。
$n,m \le5*10^5$
使用莫队的时候发现某个数字是第一次出现，就把当前数字加入到$ans$数组中，如果某个数字是第二次出现，就需要将那个数字从$ans$数组中删除，关键是出现了删除操作，使得问题变得更加复杂了。
如果我们使用平衡树来代替$ans$数组，插入和删除的时间复杂度均为$O(\log n)$那么总的时间复杂度为$O(n\sqrt n\log n)$。显然这个时间复杂度无法在规定的时间内给出答案。
根据上面我们所做出的分析，我们可以像线段树一样使用一种懒操作，即对删除操作打标记。维护一个栈，当一个元素不在栈中的时候，那他一定不在$ans$数组里面。当我们要删除某个元素的时候，只需要标记一下栈中的某个元素已被删除，即时它仍然在栈中。
那么每次询问答案的时候就依次访问栈内的元素，如果元素无效将其出栈，否则输出该元素。
上面的懒删除操作的准正确性是显然的。但是时间复杂度是多少呢？
对于每次区间移动时间开销显然是$O(1)$的，但是每次的答案统计的时间复杂度呢？每个数的只会在区间移动的时候进栈，也就是最多只有$O(n\sqrt n)$次进栈操作，而每次统计答案的时候都是出栈操作，故统计答案的总的操作数也是$O(n\sqrt n)$级别的。
综上，时间复杂度为$O(n\sqrt n)$。