P11982 题解

dAniel_lele · 2025-10-02 13:43:09 · 题解

根号重构，把所有修改了的点先拉出来，称之为特殊点。以下假设 n,q 同阶。

对于剩余点，我们发现可能满足（假定所有修改了的点 A_i=0）的一定是树形关系且有 O(n) 组这样的 (i,j)，找出来并建树。复杂度 O(n\sqrt n)。（建树是容易的，使用单调栈之类的即可）

思考一个特殊点会对这些 (i,j) 带来怎样的破坏。容易发现一个特殊点取某个值会导致树上某条链的所有二元组不符合要求。因此可以树剖线段树维护，这一部分复杂度 O(n\log^2n)。

接下来考虑特殊点与非特殊点之间的符合要求二元组该如何统计。使用 priority_queue 提前计算出每个特殊点取每个值时在非特殊点的前驱后继，复杂度 O(n\sqrt n+n\log n)。

对于特殊点之间的，每次询问时使用单调栈单独跑一遍。注意特殊点实际上前一个比他大的位置是特殊点和非特殊点的前驱位置较大的那个，后继同理。这一部分计算 O(n\sqrt n)。

总复杂度 O(n\sqrt n+n\log^2n)。