洛谷 P11398
注意到 \(\sum k \le 5 \times 10^7\)，可以在这上面做文章，复杂度大概率带一个 \(O(\sqrt k)\)
\(k\) 是一段后缀的长度，但是倒着枚举要删除数，是不好维护众数的（要带 \(\log\)）。所以要考虑转化为正着加。
但是也不能从 \(1\) 开始加。可以选取若干个关键点，枚举这些关键点，然后从关键点开始加，也就是考虑分块。
把序列分成 \(O(\sqrt n)\) 块，修改时 \(O(\sqrt n)\) 维护每个块开头 \(beg_i\) 的权值。查询时从后往前扫每个块，从 \(beg_i\) 开始向后扫过这个块内的元素，碰到了合法的位置就退出即可。每次查询最多多消耗 \(O(\sqrt n)\) 的复杂度。时间复杂度：\(O(q\sqrt n + k)\)
进一步的可以考虑倍增分块，每次查询最多多消耗 \(O(k)\) 的复杂度，总时间复杂度：\(O(q \log n + k)\)。
总结
本题的切入点就在于这个 \(\sum k\) 上，考虑到众数倒着加是无法 \(O(1)\) 维护的，就只能正着加。
如果无法从头开始枚举，可以考虑找若干个（\(O(\sqrt n)\)）关键点，也就是分块解决，使得单次不会多耗费太多代价。也就是将枚举的复杂度摊到了修改上（平衡复杂度）。