找不到在哪里提交只能口胡了。
\(\texttt{OneInDark}\) 有一个长度为 \(n\) 的序列。
这一天他找到了你，由于他很喜欢热闹，所以他想询问区间内的众数。
而且他喜欢一问一答的交互方式，所以这道题是强制在线。
因为他很强，所以他早就算出了答案，只是需要你与他对一下答案而已。
他有时候也喜欢整蛊，所以他需要你在 \(1s\) 内算出答案，不然会遭到惩罚。
\(\texttt{OneInDark}\) 还是很善解人意的，所以他不会让你很累。
区间长度和询问个数 \(n,Q\le 3*10^5\)
首先我们可以离散化。
考虑分块。
我们可以先用 \(O(n\sqrt{n})\) 的时间复杂度预处理出任意两个块之间形成的区间的众数，以及其出现次数。
我们令 \(f[l][r]\) 表示 块\(l\) 到 块\(r\) 的众数。
对于每个询问，我们考虑答案只可能是这两种情况：
在大块中。
在零散小块中。
对于第一种情况，答案就是 \(f[l][r]\)。
对于第二种情况，我们考虑零散的数只有 \(\sqrt{n}\) 级别个。
对于每个数，我们记录一下它们出现的位置(预处理)。
然后我们对于零散的数可以二分出其在区间内的出现次数。
时间复杂度为 \(O(Q\sqrt{n}logn)\)。
考虑优化。
我们令 \(pos[i][j]\) 表示 \(i\) 在数列中第 \(j\) 次出现的位置。
令 \(t[i]\) 表示 \(a[i]\) 在数列中是第几次出现。
显然我们枚举的零散的数的时候，我们可以将其当做第一次出现。
此时我们需要一个计数的变量 \(MAX\)，其初值为 \(f[l][r]\)。
如果当前枚举的这个数 \(a[i]\)，满足 \(pos[a[i]][MAX] \le qr\) (qr为询问区间的右端点)。
那么我们可以继续向右扩展，显然 \(MAX\) 总共最多只会扩展 \(\sqrt{n}\) 级别次。
\(n,Q\) 同阶，所以总时间复杂度为 \(O(n\sqrt{n})\)。
咕咕咕~
原文：https://www.cnblogs.com/PPLPPL/p/14406875.html