只有询问操作，共 $m$ 个询问，每个询问操作都是一个区间 $[l_i,r_i]$。询问区间范围为 $[1,n]$。
可以 $O(1)$ 根据当前维护区间 $[l,r]$ 更新到 $[l-1,r],[l,r+1],[l+1,r],[l,r-1]$。
则利用莫队可以 $O(n\sqrt m)$ 离线处理所有询问。
先对 $[1,n]$ 进行分块，假设每块长度为 $S$。先将 $kS\lt l_i\le (k+1)S$ 的询问丢到同一个块。
对同一个块，根据 $r_i$ 排序，然后依次处理排完序的每个询问，同时用两个指针维护当前区间。
首先对每个块，$r_i$ 单调，于是每个块移动右指针的复杂度为 $O(n)$，移动右指针的总复杂度为 $O\left(\frac {n^2}S\right)$。
同时每个左指针每次只能在所在块中移动，于是每个询问左指针的复杂度为 $O(S)$，移动左指针的总复杂度为 $O(mS)$。
于是总复杂度为 $O\left(\frac {n^2}S+mS\right)$，令 $S\sim O\left(\frac n{\sqrt m}\right)$，则总复杂度为 $O(n\sqrt m)$。
注意 每次移动指针时要先拓展指针对应的区间再缩减指针对应区间，否则对应区间长度可能会变成负数产生各种 $\text{bug}$。
给定一个长度为 $n$ 的序列，每个询问给定一个区间 $[l_i,r_i]$，询问从该区间的序列中任意取两个数，这两个数相同的概率。
双指针维护区间中的每个值的个数，同时维护当前所有使得两数相同的方案数即可。
利用奇偶化排序，即奇数块按 $r_i$ 从小到大排序，偶数块 $r_i$ 从大到小排序。
于是可以减少从一个块转移到另一个块时 $r_i$ 的移动次数，具体代码如下
struct query{ int l,r,idx; bool operator < (const query &b)const{ if(l/blk_sz!=b.l/blk_sz)return l<b.l; return ((l/blk_sz)&1)?(r<b.r):(r>b.r); } };
在普通莫队的基础上加上单点修改操作。
增加一维时间，区间变为 $[l_i,r_i,t_i]$，先根据 $l_i$ 进行分块，每个块再根据 $r_i$ 进行分块，最后对 $t_i$ 进行排序即可。
修改操作先将 $[l,r]$ 区间调整为对应区间，然后调整 $t$。对每个修改/还原操作，直接更新数组即可，注意需要记录每个操作修改前后的值。
一个技巧为每次修改/还原后调换改操作记录的修改前后的值，可以省去对修改/还原操作的分类讨论。
另外如果修改的位置属于区间 $[l,r]$，则需要对答案进行修改。
假设 $n$ 和 $m$ 同阶，首先对每个块，$t_i$ 单调，于是每个块移动时间指针的复杂度为 $O(n)$，移动时间指针的总复杂度为 $O\left(\frac {n^3}{S^2}\right)$。
同时每个左/右指针每次只能在所在块中移动，于是每个询问左/右指针的复杂度为 $O(S)$，移动左指针的总复杂度为 $O(nS)$。
于是总复杂度为 $O\left(\frac {n^3}{S^2}+nS\right)$，取取块的大小为 $O\left(n^{\frac 23}\right)$，则总时间复杂度为 $O\left(n^{\frac 53}\right)$。
给定一个长度为 $n$ 的序列，接下来两种操作。
操作 $1$ 为询问区间 $[l,r]$ 的序列中的不同的值得数量。
操作 $2$ 为单点修改。
对区间 $[l,r]$，维护每个值的个数和当前答案即可。
给定一个长度为 $n$ 的序列，接下来两种操作。
操作 $1$ 给定询问区间 $[l,r]$，设 $c_i$ 表示 $i$ 在 $a_l\sim a_r$ 中出现的次数，$s_i$ 表示 $i$ 在 $c_0\sim c_{1e9}$ 中出现的次数，求 $\text{mex}(s)$。
其中 $\text{mex}(s)$ 表示没有出现在序列 $s$ 中的最小非负整数。
操作 $2$ 为单点修改。
首先离散化一下原序列和修改操作的数值，这样数值范围变为 $O(n+q)$，同时也不会影响答案。
另外假设 $\text{mex}(s)=k+1$，则对每个 $i\in [1,k]$ 至少有一个 $j$ 满足 $c_j=i$，于是这样询问区间长度至少为 $\sum_{i=1}^k i=\frac {k(k+1)}2$。
于是 $\text{mem}(s)\sim O(\sqrt n)$。带修莫队维护 $c,s$ 序列，对每个询问暴力查询 $s$ 数组，时间复杂度 $O(n^{\frac 53}+m\sqrt n)$。
给定一个长度为 $n$ 的序列，接下来两种操作。
操作 $1$ 给定询问区间 $[l,r]$ 和整数 $k$，设 $c_i$ 表示 $i$ 在 $a_l\sim a_r$ 中出现的次数，要求选择 $k$ 个 $c_i\gt 0$，记为 $d_{1\sim k}$，最小化 $\max (d)-\min (d)$。
操作 $2$ 为单点修改。
设 $s$ 表示将 $c$ 从小到大排列的序列，于是答案变为 $\min (s_{i+k}-s_i)$。
有由于对于一个固定区间，$c_i$ 最多只有 $O(\sqrt n)$ 种取值(原因见例题 2)，于是 $s$ 最多仅有 $O(\sqrt n)$ 个值相同的段。
考虑维护 $s$ 每个段的左端点和右端点，然后双指针遍历 $s$，即可 $O(\sqrt n)$ 得到答案。
接下来考虑如何维护 $s$，当 $c_i$ 变为 $c_i+1$ 时，只需要将 $s$ 中的值等于 $c_i$ 的段的右端点的 $c_i$ 改为 $c_i+1$ 即可。
当 $c_i$ 变为 $c_i-1$ 时，只需要将 $s$ 中的值等于 $c_i$ 的段的左端点的 $c_i$ 改为 $c_i-1$ 即可。
因为最多有 $n$ 个非 $0$ 的 $c_i$，故初始时用 $n$ 个 $0$ 填充 $s$ 即可(用 $0$ 填充可以将插入操作转化为修改操作)。