UPD on 10.15：新增了一个不知名网站的一道题。
UPD on 10.1：新增了知名网站 Codeforces 的一道题。
------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------
嗯。
看到群友都学了莫队，所以我也浅学一下。
首先找 Q 群管家要了个代码，尝试自学。
他首先离线所有的询问，很正常。
然后看核心代码：
？？？？？？？？？？？？？？？？？？？？WTF
这玩意是怎么能过的？？？？？
肯定是排序暗藏玄机，看看：
嗯。。。啊？对吗？
哦对的对的。他这是按每个数左端点所处的块排序，所处的块相同再按右端点排序。然后查询就按照上一个的结果逐个改变左右端点递推处理。
左端点最多移动 O(q×block)O(q\times \text{block})O(q×block) 次，右端点总共移动 O(n2block)O(\frac{n^2}{\text{block}})O(blockn2 ) 次，在 n,qn,qn,q 同阶的情况下，当取 block=O(n)\text{block}=O(\sqrt n)block=O(n ) 时，总移动次数仅为 O(nn)O(n\sqrt n)O(nn ) 次。如果单次添加，删除的时间复杂度为 O(1)O(1)O(1) 的话，总时间复杂度就是 O(nn)O(n\sqrt n)O(nn )。
甜菜啊！
当然，n,qn,qn,q 不同阶的情况下可以考虑取 block=nqq\text{block}=\frac{n\sqrt q}{q}block=qnq ，这样时间复杂度就是 O(nq)O(n\sqrt q)O(nq )，最优。
话不多说，直接洛谷找一个莫队蓝题做做。
P1494 小 Z 的袜子
显然，原问题可以转化成选取任意两个袜子颜色相同的方案数除以总方案数的结果。显然分母为 (r−l+1)×(r−l)2\frac{(r-l+1)\times(r-l)}{2}2(r−l+1)×(r−l) ，问题的关键就在于如何求分子了。
注意到我们可以这样做：
开一个桶 bucket\text{bucket}bucket，记录区间内每个数记录的个数。
添加 xxx：答案增加 bucket[x]\text{bucket}[x]bucket[x]，然后使 bucket[x]\text{bucket}[x]bucket[x] 增加 111。
删除 xxx：使 bucket[x]\text{bucket}[x]bucket[x] 减小 111，然后使答案减小 bucket[x]\text{bucket}[x]bucket[x]。
然后写一下莫队就行了。
时间复杂度：O(nn)O(n\sqrt n)O(nn )。
------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------
然后，我想到了一个更逆天的东西。
注意到树状数组可以当做集合，O(logn)O(\log n)O(logn) 添加元素删除元素在线求第 kkk 小。
树状数组+莫队=？区间第 kkk 小！
那时间复杂度是多少呢？显然，是 O(nnlogn)O(n\sqrt n\log n)O(nn logn)。注意到 105×⌈105⌉×⌊log2105⌋=5.072×10810^5\times \lceil\sqrt{10^5}\rceil\times \lfloor\log_2 10^5\rfloor=5.072\times 10^8105×⌈105 ⌉×⌊log2 105⌋=5.072×108，只要常数够小甚至可以在 111 秒内通过 10510^5105 的数据！
理论存在，实践开始。
P3834 【模板】可持久化线段树 2，目标：80PTS
思路已经讲的差不多了，直接贴代码。
注意值域，需要离散化。
结果：挑战成功，甚至通过了该题。（绷）
------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------
实战演练，直接拿最近一场 Div3 的最后一题举例。
CF2149G BURATSUTA 3
题意解析：给定一个数组 AAA 和 qqq 次询问，每次询问一个区间 [l,r][l,r][l,r]，请你输出 [l,r][l,r][l,r] 中所有出现超过 13\frac{1}{3}31 的数。
考虑莫队。
我们需要维护的内容如下：
* AiA_iAi 在区间内出现的次数。
* 出现次数为 iii 的数有哪些。
* 区间内有多少个出现超过 13\frac{1}{3}31 的数。
显然可以用 set 通过添加和删除 O(logn)O(\log n)O(logn) 维护，十分方便。
但是——注意数据范围，n,q≤2×105n,q\le 2\times 10^5n,q≤2×105，总时间复杂度就是 O(nnlogn)O(n\sqrt n\log n)O(nn logn) 的，在 2×1052\times 10^52×105 的数据下总运行次数约为 1.6×1091.6\times 10^91.6×109，再叠加上 set 的大常数直接 T 飞了。我们需要更快速的数据结构。
我们可以使用一个冷门数据结构——list！它是用链表实现的，可以支持 O(1)O(1)O(1) 在线插入、删除某个元素。
这时，我们需要的变量如下：
* int times[n]：储存 AiA_iAi 在区间内出现了多少次。
* list <int> bucket[n]：储存出现次数为 iii 的数有哪些。
* list <int>::iterator idxs[n]：迭代器，储存 AiA_iAi 在 bucket 的哪个位置。
* list <int> curans：储存区间内有多少个出现超过 13\frac{1}{3}31 的数。
* bool inans[n]：由于不是 set 不能自动去重，所以需要用一个数组储存 AiA_iAi 是否已出现在答案中。
接下来就是折磨代码环节了。
时间复杂度 O(∑nq)O(\sum n\sqrt q)O(∑nq ) 。
结果：卡常失败，TLE on 5。
我常数大点怎么了555555555555555
------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------
注意到某个不知名网站新出了一个 APC（A*** Peak Contest），这场比赛中有一道题挺有意思的，并且可以使用莫队做，所以我就来写一篇题解。
题意解析：
给定一颗大小为 nnn，根为 111 的树，树上的每个节点有一个颜色 AiA_iAi ，给出 qqq 次询问，每次询问一个节点，问它的子树中有多少种颜色出现次数 ≥k\ge k≥k。
------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------
注意到一个节点的子树的 dfn\text{dfn}dfn 是连续的，所以我们可以先随便 dfs\text{dfs}dfs 一下，将 AdfniA_{\text{dfn}_i}Adfni 变成 AiA_iAi ，然后把问题转化成求区间有多少种颜色出现次数 ≥k\ge k≥k。n,q≤2×105n,q\le 2\times 10^5n,q≤2×105。
考虑莫队。
有个很显然的方法就是开一个 map 和一颗树状数组，然后 O(logn)O(\log n)O(logn) 单点更新。
但是这样就和前面的区间第 kkk 小的解法重复了，学不到任何新东西 ，而且还不好水创作计划。
我们可以新增一维 kkk，然后当作 333 维莫队实现。
333 维莫队的排序方式和 222 维差不多：
* 先按第一维所在的块为第一关键字。
* 然后再按第二维所在的块为第二关键字。
* 最后按第三维作为第三关键字。
当然，为了卡常，我们可以分奇偶排序，减小移动次数。
这个时候，块长应该取多少合适呢？
没错，就是 O(n23)O(n^{\frac{2}{3}})O(n32 )，这样第一维、第二维每次询问都得移动 O(n23)O(n^{\frac{2}{3}})O(n32 ) 次，因为一共有 O(n2/(n23)2)=O(n23)O(n^2/(n^{\frac{2}{3}})^2)=O(n^{\frac{2}{3}})O(n2/(n32 )2)=O(n32 )，所以第 333 维总共移动 O(n×n23)O(n\times n^{\frac{2}{3}})O(n×n32 ) 次。总时间复杂度为 O(n53)O(n^{\frac{5}{3}})O(n35 )，在 n=2×105n=2\times
10^5n=2×105 时运行约 6.8×1086.8\times 10^86.8×108 次，足够了。
具体实现：
dfn\text{dfn}dfn 转化：
单点加/删（由于不考虑大于等于 000 的情况，所以 bucket2[0] 设什么值都不影响）：
kkk 增加/减少 111：
经过一番调试，我发现块长在 400400400 左右时是最优的。
总代码如下：
