题解：P5511 决战

Solwek · 2026-04-24 16:35:59 · 题解

口胡的，没写代码，太难写了，后面可能会补。

考虑前 3 个测试点怎么做，考虑分块，设块长为 B。

每个块维护块内排序后的序列，操作时整块可以直接打标记，散块重构，可以使用归并排序，所以复杂度为 O(B+\frac{n}{B})。对于询问，散块直接求和整块根据标记二分即可，时间复杂度 O(B+\frac{n\log n}{B})，取 B=\sqrt {n\log n}，总时间复杂度 O(n\sqrt {n\log n})。

但是一开始的 n 比较大，直接分块会炸掉，而且不能离线。因为只会有 O(m) 个连续段，所以考虑操作分块，设当前序列分块块长为 B_1，操作分块块长为 B_2，那么每次最多会增加 B_2 个段，那么预处理复杂度为 O(\frac{m^2\log m}{B_2})，操作复杂度为 O(B_1+B_2+\frac{n}{B_1})，询问复杂度为 O(B_1+B_2+\frac{n\log n}{B_1})，取 B_1=B_2=\sqrt {m\log m}，总时间复杂度 O(m\sqrt {m\log m})。

常数看起来会比块状链表小很多。