ARC197C

Fearlessy · 2025-11-20 18:57:19 · 题解

什么神秘题。

正常做感觉不太能做。注意到 B_i \le 10^5。考虑在这上面做文章。我们考虑答案最大能到多少。

显然每次删质数删的是最多的。假设 10^5 次操作每次都删了一个质数，那么最后一次查第 10^5 小的数，答案的最大值就不会超过第 2\times 10^5 个质数。实际会更小。这个很好理解。

本地算一下第 2 \times 10^5 个质数是 2750159。是 V = 3 \times 10^6 量级。于是可以暴力修改。调和级数证明暴力修改是 \mathcal{O(n\ln n)} 的。注意不要重复修改同个数。

考虑查询。容易想到二分答案。咋判断 x 是否还在呢？使用值域 bit 维护 [x,V] 中数出现的个数即可。时间复杂度 \mathcal{O(n \log^2 n)}。

实际上可以使用值域 sgt。在 sgt 上二分可以去掉一个 log。不过得益于 sgt 的大常数两个东西跑的应该差不多快。

Submission