P14449 [ICPC 2025 Xi'an R] Catch the Monster

发现链一定可以，我们只需要从左到右扫过去即可。然后考虑向外扩展，发现扩展一个没有关系，因为只要经过的时候往里探一下即可。但是发现如果再深，那么在往里探的时候如果怪物在链上，那么它可以跨过也可以选择不跨过。那么我们回去的时候它就不一定会在哪个方向，我们就不知道该向哪里走了。整理一下形状，就发现当且仅当不存在 \(3\) 个相邻节点的度数都大于等于 \(2\)。

那么之后考虑查询，发现如果一个子区间不行了那么所有包含这个区间的都不行。那么很容易想到双指针每一个右端点所能够对应的最长合法区间 \((l,r_i)\)。考虑加入一个点，那么：

1. 它自己可能会将三个度数大于等于 \(2\) 的点连起来。
2. 它自己度数大于等于 \(2\)，对旁边的点有贡献。
3. 它旁边的点度数会增加，那么如果旁边的点度数从 \(1\) 变成了 \(2\)，则会对它旁边的点的旁边的可能非法答案加 \(1\)。

那么删除就是类似的，将贡献变为负数即可。