题解：P15589 [KTSC 2026] 瞭望塔 / Observation Tower

· · 题解

小清新分块题。

首先我们能很容易地看出来，对于一个人 i 其能看到的人一定是以 i 为起点的严格前缀最值，那么我们直接就能得到一个暴力 O(nq) 的做法。

感觉这些部分分都对正解没啥太大的启发意义，直接讲做法吧。

看到 n,q 不同阶，还有这么复杂度的信息维护，我们直接考虑序列分块。

对于操作 1，我们直接暴力先枚举其所在块的后缀散块更新。对于后面的整块我们发现只有整块内部的前缀最值有用，我们只把每个块的前缀最值提取出来，那么整块操作只会对这些人的一段后缀加一，直接打标记即可。

对于操作 2，散块先暴力下放标记，然后直接查询。整块直接维护答案和即可。

对于操作 3，整块修改不会影响块内的前缀最值，直接打标记。散块我们直接暴力下放所有标记然后重构前缀最值即可。

综上，我们的复杂度瓶颈在于操作 1 中找到每个整块操作的后缀，这个东西你直接做是需要二分的，所以不优化的复杂度是 O(q\sqrt {n\log n})，显然是不优秀的，考虑怎么优化。（但是直接写这个东西就能过）

我们相当于每个块我们每次需要查询第一个 >k 的地方，我们发现我们是可以提前求出这个 k 的。直接考虑离线逐块处理，如果我们不存在块重构操作，那么我们对于每个块把询问按 k 排序，然后就可以双指针求解了。然后有块重构操作，只是相当于重置了指针，会多出 O(\sqrt n) 的势能，总势能还是 O(q\sqrt n) 的，然后这个排序我们直接基排就行了，令 \omega=10^6\sim 10^7 即可。

综上时空都是 O(q\sqrt n)，空间开不下就调一下块长。

因为我也没有实现下面这种做法，有什么细节上的问题可以私信我。

代码写得太丑就不放了。

后记：std 怎么是 Polylog 的？