自动搬运

查看原文

来自洛谷，原作者为

	dead_X Still we rise

搬运于2025-08-24 22:47:48，当前版本为作者最后更新于2023-05-31 11:15:12，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

低情商：垃圾题。

高情商：颇有联考风范。

算了，可能是我对有趣的 DS 已经产生了足够扭曲的认识吧。

首先将所有数全部转 $B$ 进制变成字符串，然后操作就是 push_back，pop_back。

显然最后所有数都会变成某个数的一段前缀，记最后变成了 $a_x[1,y]$，我们只需要统计 $\sum\limits_{t=1}^y\sum\limits_{i=l}^r[a_i[1,t]=a_x[1,t]]$ 即可，单次统计等价于 $\log a$ 次矩形查询，使用主席树可以做到 $\log^2 a$。

不难发现 $\sum\limits_{i=l}^r[a_i[1,t]=a_x[1,t]]$ 要 $\geq\frac{r-l+1}{2}$ 才是更优的，因此我们随机选一个数有 $\frac{1}{2}$ 的概率选到答案，选 $\log n+\log m$ 个数即可保证正确率。

随机选择一个数后一位一位扫判断 $\sum\limits_{i=l}^r[a_i[1,t]=a_x[1,t]]\geq\frac{r-l+1}{2}$ 是否成立即可，时间复杂度 $O(n(\log n+\log m+\log a)\log^2 a)$。