题解：P6526 「Wdoi-1」四重存在

题解区有两篇线段树做法的题解，复杂度 $O(m \log m)$。还有一篇线性做法的题解，但我好像没怎么看懂，于是自己写了一个和那篇题解不太一样的其他线性做法。

设 $f(i)$ 表示 $i$ 是后一个点时的最大值，$g(i)$ 表示此时前一个点的编号，$f'(i)$ 表示 $i$ 是后一个点时的非严格次大值。

考虑插入一个点时如何快速处理 $f, g, f'$ 三个数组。曼哈顿距离不好处理，考虑转成切比雪夫距离。然后我们实时维护八个点代表 $x, y$ 方向上的最大 / 次大 / 最小 / 次小值，利用这些信息可以在 $O(1)$ 时间内快速处理出 $f, g, f'$ 三个数组。

对于 $2$ 询问，显然问的是 $f$ 的全局最大值，直接维护即可，接下来考虑如何处理 $3$ 询问。

显然对于某次询问，如果此时有 $n$ 个点，询问时删除了第 $x$ 号点，显然答案应该是：

为什么次大值 $f'$ 那里不需要考虑是从哪个点转移来的？因为如果次大值是从 $x$ 转移来的，那么最大值一定不是从 $x$ 来的。最大值严格不小于次大值，所以就算统计了非法的次大值也不会对答案产生影响。

第一部分可以直接处理前缀和 $O(1)$ 查询。但实际上我们不需要维护前缀和查询第一部分，这一部分我们可以一会儿扔到第三部分一起做。

第二部分看起来是个查询后缀和，但我们注意到因为 $f'(i) \le f(i)$，因此就算把 $\max_{i = 1}^{x - 1} f'(i)$ 统计进来也不会对答案产生影响。所以其实第二部分就是：

换言之，就是查询整个 $f'$ 序列除了 $x$ 位置的最大值。

我们维护 $f'$ 序列的最大值，最大值的位置和次大值即可 $O(1)$ 查询。

现在难的是第三部分，如何 $O(1)$ 查询？

注意到第一部分的 $\max_{i = 1}^{x - 1} f(i)$，由于 $x$ 前面的所有数 $g$ 都不可能是 $x$，所以在后面乘上 $[g(i) \neq x]$ 也不会影响。

那么第一部分和第三部分可以合起来，长这样：

其实这就是：

这个东西怎么处理？

处理出 $f$ 的最大值，假设这个最大值为 $f(i)$。找到 $g(j) \neq i$ 的最大 $f(j)$ 和 $k \neq g(i)$ 且 $g(k) \neq g(i)$ 的最大 $f(k)$。当 $x = i$ 时答案为 $f(j)$，当 $x = g(i)$ 时答案为 $f(k)$，其他情况下答案为 $f(i)$，回答询问是 $O(1)$ 的。

并且我们发现在插入一个新 $f, g$ 的时候我们可以 $O(1)$ 更新 $f(i), f(j)$ 和 $f(k)$。具体做法如下：

设插入的数为 $y$。

显然这些东西都是 $O(1)$ 的。

每一步操作都是 $O(1)$ 的，总复杂度自然是 $O(n)$ 的。

于是我们得到了一个线性做法，跑得还是飞快的，截至目前还是本题最优解来着。