题解：P6526 「Wdoi-1」四重存在
AC_love
·
·
题解
题解区有两篇线段树做法的题解，复杂度 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 号点，显然答案应该是：
\max(\max_{i = 1}^{x - 1} f(i), \max_{i = x + 1}^n f'(i), \max_{i = x + 1}^n f(i) \times [g(i) \neq x])
为什么次大值 f' 那里不需要考虑是从哪个点转移来的？因为如果次大值是从 x 转移来的，那么最大值一定不是从 x 来的。最大值严格不小于次大值，所以就算统计了非法的次大值也不会对答案产生影响。
第一部分可以直接处理前缀和 O(1) 查询。但实际上我们不需要维护前缀和查询第一部分，这一部分我们可以一会儿扔到第三部分一起做。
第二部分看起来是个查询后缀和，但我们注意到因为 f'(i) \le f(i)，因此就算把 \max_{i = 1}^{x - 1} f'(i) 统计进来也不会对答案产生影响。所以其实第二部分就是：
\max(\max_{i = 1}^{x - 1} f'(i), \max_{i = x + 1}^n f'(i))
换言之，就是查询整个 f' 序列除了 x 位置的最大值。
我们维护 f' 序列的最大值，最大值的位置和次大值即可 O(1) 查询。
现在难的是第三部分，如何 O(1) 查询？
注意到第一部分的 \max_{i = 1}^{x - 1} f(i)，由于 x 前面的所有数 g 都不可能是 x，所以在后面乘上 [g(i) \neq x] 也不会影响。
那么第一部分和第三部分可以合起来，长这样：
\max(\max_{i = 1}^{x - 1} f(i) \times [g(i) \neq x], \max_{i = x + 1}^n f(i) \times [g(i) \neq x])
其实这就是：
\max_{i = 1}^n f(i) \times [i \neq x] \times [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。
- 若 f(y) > f(i)
- 若 g(y) = i
- 若 g(k) = i，则 f(k) \leftarrow f(j), f(j) \leftarrow f(i), f(i) \leftarrow f(y)
- 反之，若 g(k) \neq i，则 f(k) \leftarrow \max(f(j), f(k)), f(j) \leftarrow f(i), f(i) \leftarrow f(y)
- 反之，若 g(y) \neq i，但 g(y) = g(i)
- 若 g(j) = g(i) 或 j = g(i)，则 f(k) 不变，f(j) \leftarrow f(i), f(i) \leftarrow f(y)
- 反之，则 f(k) \leftarrow \max(f(j), f(k)), f(j) \leftarrow f(i), f(i) \leftarrow f(y)
- 反之，则 f(k) \leftarrow f(i), f(j) \leftarrow f(i), f(i) \leftarrow f(y)
- 否则则判断能否用 f(y) 更新 f(j) 和 f(k) 即可。
显然这些东西都是 O(1) 的。
每一步操作都是 O(1) 的，总复杂度自然是 O(n) 的。
于是我们得到了一个线性做法，跑得还是飞快的，截至目前还是本题最优解来着。