PKUWC2025 D2T3 题解

· · 个人记录

重生之随便写个暴力成为全场唯一通过。

考虑操作逆序，+1,-1 互换，乘以 k 变成整除 k。

考察什么样的数可以由 l\sim r 做不超过 B 次操作得到，可以发现只有在形如 [\max(l/y-B,1),r/y+B] 这样的区间里的数可以被取到，其中 y 是正整数。（这里不要求整除）

设这些区间的并为集合 S，可以发现集合 S 有这样的性质：对于任意 z\in S，任意 w \mid z 也满足 w\in S。证明就是考虑取出任意一个包含 z 的区间 [l/y-B,r/y+B]，设 z=aw，那么 w\in [l/(ay)-B,r/(ay)+B]。

考虑分析集合 S 的大小，对 y 进行分类讨论。

对于 y> \sqrt{r/B}，我们有 r/y+B<\sqrt{Br}+B。

对于 y\leq \sqrt{r/B}，直接计算区间长度之和：

\sum_{y=1}^{\sqrt{r/B}}\left(\frac{r-l}{y}+O(B)\right)=O((r-l)\ln(r-l)+\sqrt{Br})

因此 S 的大小是 (r-l)\ln(r-l)+\sqrt{Br} 级别。

求出 S 集合内的所有数可以直接暴力枚举小的 y，然后拼上 \sqrt{Br}+B 内的所有数，因为区间关于 y 单调所以去重是简单的。

求出 S 集合后，考虑怎么做原问题。

暴力怎么做，维护 1\sim r+B 的答案，B 次狄利克雷前缀和直接转移。

因为这题做法是暴力，所以还是狄利克雷前缀和直接转移。

现在就有两个问题，一个是怎么求出所有刚好差了质数倍的转移对 u,v，另一个是分析总对数的级别。

考虑把 S 集合分成两部分，把 >\sqrt{Br} 的称为大集合，反之称为小集合。

小集合内的转移数显然不超过 \sqrt{Br}\log\log r，且容易求出，而大集合内每个数对应的 y 都不超过 \sqrt{r/B}，因此它一定是 [l-\sqrt{Br},r+\sqrt{Br}] 内某个数的因数。

因此我们只需对这个区间跑区间筛，然后只需要解决对于一个集合内的 u，定位 u/p 在集合里的位置。

可以发现只需要知道 u 所在区间的 y，并记录每个 y 对应的区间左端点位置即可，复杂度应该是 O(1) 的。

听说转移数可以分析出是 |S|\log\log r，但是我没学会。

这样的总复杂度就是 O(B(\sqrt{Br}+(r-l)\ln (r-l))\log \log r)，可以通过。

不过我赛时写的是对每个区间区间筛，还有一百万个 map 去重，这样居然也通过了。