时间复杂度 O \left( n \log n + n t ^ 2 + m d \right)，空间复杂度 O \left( n t ^ 2 \right)。由
O \left( n t ^ 2 + m d \right) = O \left( \dfrac {n ^ 3} {d ^ 2} + m d \right) = O \left( \dfrac {n ^ 3} {d ^ 2} + m d + m d \right) \ge O \left( \sqrt [3] {n ^ 3 m ^ 2} \right) = O \left( n m ^ {\frac 2 3} \right) .
等号成立时 \dfrac {n ^ 3} {d ^ 2} = m d，即 d = \dfrac n {\sqrt [3] m}。
于是，取 d = \dfrac n {\sqrt [3] m}，t = \sqrt [3] m 时，时间复杂度 O \left( n \log n + n m ^ {\frac 2 3} \right)，空间复杂度 O \left( n m ^ {\frac 2 3} \right)，在洛谷上已经可以 AC 了。
（代码链接在文末）
小细节
处理每次询问时，不能用 memset 或 memcpy 对一个大小为 O \left( n \right)（离散化后的值域）的数组进行赋值，否则会破坏这部分 O \left( m d \right) 的时间复杂度。
正确的做法是：直接在对应 Cnt _ {i , j} 的基础上修改，统计结束后，重新扫描一遍涉及的元素，并减去其计数，即恢复原状态。
考虑对每个数值 w 开一个动态数组v _ w \left( k \right)，记录其在 a _ 1 \sim a _ n 中出现的所有位置。
这样，要查询数值 w 在 a _ l \sim a _ r 中出现的次数，在 v _ i 中二分查找第一个大于r 的位置和第一个大于等于l 的位置，二者相减，即为答案。
剩下的操作就和方法一基本相同了。
时间复杂度 O \left( n \log n + n t + m d \log n \right)，空间复杂度 O \left( n + t ^ 2 \right)。由
O \left( n t + m d \log n \right) = O \left( \dfrac {n ^ 2} d + m d \log n \right) \ge O \left( \sqrt {n ^ 2 m \log n} \right) = O \left( n \sqrt {m \log n} \right) .
等号成立时 \dfrac {n ^ 2} d = m d \log n，即 d = \dfrac n {\sqrt {m \log n}}。
注意二分查找的 \log 底数取 2 较合适。于是，取 d = \dfrac n {\sqrt {m \log _ 2 n}}，t = \sqrt {m \log _ 2 n} 时，时间复杂度 O \left( n \log n + n \sqrt {m \log n} \right)，空间复杂度 O \left( n + m \log n \right)。
小细节
虽然理想块长为 d = \dfrac n {\sqrt {m \log _ 2 n}}，但不建议在程序中直接写 n/sqrt(m*log2(n))！
当 n = 1 时，\log _ 2 n = 0，引发除数为 0。浮点数除数为 0 不会直接报错，根据程序原理，结果可能正确，可能异常。
使用 n/sqrt(m*log2(n+1)) 可以回避这个问题。
设 \left[ l , r \right] 对应的连续整块为第 i \sim j 块，Cnt \left( w \right) 为数值 w 在非整块中出现的次数，则 w 在 a _ l \sim a _ r 中出现的次数为
S _ j \left( w \right) - S _ {i - 1} \left( w \right) + Cnt \left( w \right).
运用这个值，在经方法二预处理得到的 Mode _ {i , j} 基础上更新众数即可。
时间复杂度 O \left( n \log n + n t + m d \right)，空间复杂度 O \left( n t \right)。由
O \left( n t + m d \right) = O \left( \dfrac {n ^ 2} d + m d \right) \ge O \left( \sqrt {n ^ 2 m} \right) = O \left( n \sqrt m \right) .
等号成立时 \dfrac {n ^ 2} d = m d，即 d = \dfrac n {\sqrt m}。
于是，取 d = \dfrac n {\sqrt m}，t = \sqrt m 时，时间复杂度 O \left( n \log n + n \sqrt m \right)，空间复杂度 O \left( n \sqrt m \right)。
方法四
方法三的时间复杂度优于方法二，但空间复杂度反而劣于方法二（对数变成了根号）。我弱校 OJ 上 AC 不了。
注意到 S _ i \left( w \right) 占用空间太大，这使我们想要请回动态数组 v _ w \left( k \right)。但二分查找的问题又横在我们面前。
如果预处理每个 a _ x 在 v _ {a _ x} \left( k \right) 中出现的位置 u _ x，那么，当查询 w 在 a _ l \sim a _ r 中出现的次数时，如果 a _ l = w且a _ r = w，则答案为 u _ r - u _ l + 1。
现在问题是：a _ l = w 且 a _ r = w 不一定满足。
但是，对每个 \left[ l , r \right] 划分出的非整块至多只有首尾两个。对首块扫描到 a _ x，一定有 \left[ x , r \right] \subseteq \left[ l , r \right] 且 a _ l = w（不是从前到后第一次出现的元素，其贡献可以直接忽略）；对尾块扫描到 a _ x，一定有 \left[ l , x \right] \subseteq \left[ l , r \right] 且 a _ r = w（不是从后到前第一次出现的元素，其贡献可以直接忽略）。