2025-2026:teams:the_server_is_busy_please_try_again_later:20250731
差别
这里会显示出您选择的修订版和当前版本之间的差别。
| 两侧同时换到之前的修订记录 前一修订版 | |||
|
2025-2026:teams:the_server_is_busy_please_try_again_later:20250731 [2025/08/03 12:05] ender_hz |
2025-2026:teams:the_server_is_busy_please_try_again_later:20250731 [2025/08/22 19:44] (当前版本) istina |
||
|---|---|---|---|
| 行 71: | 行 71: | ||
| 由于 $n(n-1) +m$ 较大，计算时使用 Lucas 定理后做 $2m$ 次运算即可，时间复杂度 $\mathcal O(m\log P)$。 | 由于 $n(n-1) +m$ 较大，计算时使用 Lucas 定理后做 $2m$ 次运算即可，时间复杂度 $\mathcal O(m\log P)$。 | ||
| + | |||
| + | ==== E（_istina_ 补）==== | ||
| + | 考虑朴素的分块。记块长为 $L$ ，$a$ 的第 $i$ 个块为 $A_i$ ，$a_p$ 的第 $i$ 个块是 $B_i$ 。 | ||
| + | |||
| + | 再记 $A_i$ 整块加一后 $B_j$ 的增量为 $f_{i, j}$ 。并对 $f_i$ 做前缀和 $S_{i, j}$ 。（可以在预处理时 $\mathcal O(n + (\frac{n}{L})^2)$ 求得） | ||
| + | |||
| + | 修改涉及整块时，对 $A_i$ 维护一个懒标记 $tag_i$ ，则其对 $B_{l..r}$ 的影响之和为 $tag_i \sum_{j = l}^{r}f_{i,j}$ ，即 $tag_i (S_{i, r} - S_{i, l - 1})$ 。至于不成整块的部分，直接暴力修改。单次修改时间复杂度为 $\mathcal O(\frac nL + L)$ 。 | ||
| + | |||
| + | 查询时类似。整块用懒标记统计增量，不成整块的部分直接暴力统计。单次修改时间复杂度也为 $\mathcal O(\frac n L + L)$ 。 | ||
| + | |||
| + | 取 $L = \sqrt n$，则总时间复杂度为 $\mathcal O(n + q\sqrt n)$ ，可以通过本题。 | ||
| + | |||
| ==== F（Ender_hz 补）==== | ==== F（Ender_hz 补）==== | ||
2025-2026/teams/the_server_is_busy_please_try_again_later/20250731.txt · 最后更改: 2025/08/22 19:44 由 istina
