题解 P9376

dead_X · 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)。