2025.01.10 杂题记录

CF1998E2

这题是求能否吃完，而不是最多吃多少个。

首先如果 \(x=n\)，那么是经典问题，每次往左右二分一个位置扩展，每次扩展两次和都会翻倍，复杂度就是 \(O(n\log n\log V)\)。

我们考虑每个起始点对每个 \(f(i)\) 的贡献。我们每次应当优先往左扩展，如果扩展不了，往右扩展时应当扩展到第一个使得能再往左扩展的位置，二分找到这个位置然后尝试扩展到这个位置。重复这个过程直到左边吃到 \(1\)，这样我们就能求出第一个满足可以吃到 \(1\) 的右端点。之后继续往右扩展找到最后一个满足的右端点。

这样我们发现每个起始点对 \(f(i)\) 的贡献，\(i\) 是一个区间，差分贡献答案。

这样时间复杂度还是 \(O(n\log n\log V)\) 的。

P5445 [APIO2019] 路灯

考虑用连通块的左右端点 \(l\) 和 \(r\) 放到二维平面上，用点 \((l,r)\) 表示一个连通块，把点带上贡献，再带上时间一维，那么查询 \(L,R\) 就变成了一个三维偏序问题，要满足 \(l\le L\land R\le r\) 且时间在询问之前。这部分可以 CDQ分治 解决。

我们可以用 set 维护当前每个连通块，一次插入点或删点会产生 \(O(1)\) 个变化，set 中还要记录连通块形成的时间以计算贡献。

发现如果询问时 \(L,R\) 在一个连通块内，这部分的贡献不好在偏序中计算，这部分可以直接在询问时在 set 中查询计算。

时间复杂度 \(O(n\log ^2n)\)，瓶颈在分治。

P4269 [USACO18FEB] Snow Boots G

水题。靴子不能跨过，当且仅当，小于等于 \(s_i\) 的雪之间最大的间隔不超过 \(d_i\)。

考虑离线下来以后，将靴子和雪都按高度排序，然后双指针加入雪和查询靴子，用 set 维护相邻雪堆的间隔与间隔的最大值。

时间复杂度 \(O(n\log n)\)。

[NOISG2022 Qualification] Dragonfly

考虑离线下来，因为一个节点权值为 \(0\) 后就没有贡献了，那么考虑求出最后能产生贡献的时刻 \(t_i\)。

那么能吃节点 \(i\) 的询问在 \(i\) 的子树内。考虑以时间为下标建线段树，询问就在这个询问所在的时间插入一个点，那么我们可以自底向上线段树合并，合并到点 \(i\) 时在线段树上二分即可求出 \(t_i\)。这一部分的线段树只需维护一个子树大小。这一部分是 \(O(d\log d)\) 的。

求出 \(t_i\) 后，对于第 \(j\) 个询问，我们就是求满足下列条件的颜色个数：从 \(1\) 到 \(h_j\) 路径上存在这种颜色的点 \(i\) 使得 \(t_i\ge j\)。

考虑从根开始遍历，进入一个节点就插入这个节点的贡献，离开子树就撤销贡献。

我们现在就想知道从 \(1\) 到当前点的路径上，每种颜色 \(t\) 的最大值是多少。然后每次最大值更新时用数据结构维护一下即可。

由于如果存在颜色相同的 \(i,j\) 满足 \(i\) 是 \(j\) 的祖先，且 \(t_i\ge t_j\)，那么 \(j\) 是没有用的。所以考虑对每种颜色开一个栈，当 \(t\) 大于栈顶时才推进栈中，然后用一个以 \(t\) 为下标的树状数组维护：有多少种颜色的 \(t\) 大于等于某个数。

这一部分也是 \(O(d\log d)\) 的。

然后就做完了，最终的复杂度就是 \(O(d\log d)\) 的（这里我们设 \(n,d\) 同阶）。