summer

Problem

Solution

挺好的题，题解也写得很清楚，因此我不过是把题解抄一遍。

赛时打了 \(40\) 分，然后挂了 \(20\) 分，因为不会前缀和（这个人暴力求区间和，铸币吧）。

前 \(40\) 分就是记忆化搜索 + 单调栈：

首先考察对于一个确定的序列，如何求出一段区间的权值和。那么首先就要知道如何快速计算一个点的权值和。

权值由两部分组成：

• 加入新点，这部分权值是固定的，必为 \(n - 1\)。

• 改变捕虫网能力值，贪心地考虑这个能力值只增不减，很快得到以下做法：

设 \(f_x\) 表示在 \(x\) 起始时至少要更改几次捕虫网的能力值。

对于 \(f_x\)，求出左侧最大的 \(lp_x\) 使得 \(a_{lp_x} > a_x\)（若没有则记 \(lp_x = 0\)），求出右侧最小的 \(rp_x\) 使得 \(a_{rp_x} > a_x\)（若没有则记 \(rp_x = n + 1\)）。为方便表示，记 \(l = lp_x, r = rp_x\)。

• \(a_l < a_r\) 时：\(f_x = f_l + 1\)
• \(a_l > a_r\) 时：\(f_x = f_r + 1\)
• \(a_l = a_r\) 时：\(f_x = \max(f_l, f_r) + 1\)

初始值：\(f_0 = f_{n + 1} = -1\)。

可以通过记忆化搜索对确定的序列 \(O(n)\) 求出 \(f\)。

但是题解对于这个做法有一个更加形式化的描述，我认为很不错：

设 \(L_x\) 表示 \(a_1, a_2, \dots, a_x\) 的后缀最大值集合，\(R_x\) 表示 \(a_x, a_{x + 1}, \dots, a_n\) 的前缀最大值集合，那么 \(f_x = |L_x \cup R_x| - 1\)。（减 \(1\) 是要减去 \(a_x\) 本身。）

这个说法使得之后想正解更加清晰。

只交换相邻两个数，想到了维护变化量，也想到了这道题可能要用数据结构维护，但是赛时把暴力打完就跑了（四道题里面分打得最多的一道）

交换 \(a_x, a_{x + 1}\)：

• 若 \(a_x = a_{x + 1}\)：显然没有影响。

• 若 \(a_x < a_{x + 1}\)：

  • 对于 \(i < x\)：显然对 \(L_i\) 没有影响，于是只考虑 \(R_i\)。

    交换后，影响只有一种可能：将 \(a_x\) 在某些 \(R_i\) 中删除。

    \(R_i\) 被影响到 \(\iff\) \(\max\limits_{j = i}^{x - 1}a_j < a_x\)。（注意不要取等！）

    \(\max\limits_{j = i}^{x - 1}a_j\) 随 \(i\) 变大而减小，所以被影响到的区间可以通过二分求出。由于 \(a\) 数组是在变化的，因此需要用数据结构维护，可以用线段树二分求出被影响的区间。

    假设已经求得被影响的区间是 \([l, r]\)，那么怎么执行影响呢？维护集合太难了，考虑直接维护 \(f_i\)。但还要注意 \(L_i\) 对 \(f_i\) 的影响，这里又用到了一步简单而巧妙地判断：

    • 若 \(a_{l - 1} = a_x\)，则 \(\forall i \in [l, r], a_{x} = a_{l - 1} \in L_{i}\)，\(f\) 不变。
    • 否则，因为 \(a_{l - 1} \ge a_x\)（被影响区间的定义），所以必然有 \(a_{l - 1} > a_x\)，而 \([l, r]\) 内不存在 \(a_x\)，所以 \(\forall i \in [l, r], a_{l - 1} \in L_i, a_x \not\in L_i\)，区间 \([l, r]\) 的 \(f\) 值减 \(1\)。

  • 对于 \(i > x + 1\)：同理，对 \(R_i\) 没有影响，但是对 \(L_i\) 有影响。

    交换带来的影响为，将 \(a_x\) 加入某些 \(L_i\)。

    \(L_i\) 被影响到 \(\iff\) \(\max\limits_{j = x + 1}^{i}a_j < a_x\)。

    类似地处理即可。

  • 对于 \(i = x\) 和 \(i = x + 1\)：如果用 \(f_x = |L_x \cup R_x| - 1\) 的定义，似乎不太好操作，可以考虑通过原始的求法更新 \(f_x, f_{x + 1}\)。

    现在问题在于如何快速得到 \(lp_x, rp_x, lp_{x + 1}, rp_{x + 1}\)。这不还是线段树二分？

    完结撒花。但还是把 \(a_x > a_{x + 1}\) 的情况写一下。

• 若 \(a_x > a_{x + 1}\)：

  • 对于 \(i < x\)：对 \(L_i\) 无影响，对 \(R_i\) 的影响为：将 \(a_{x + 1}\) 插入某些 \(L_i\)。

    \(L_i\) 被影响到 \(\iff\) \(\max\limits_{j = i}^{x - 1}a_j < a_{x + 1}\)。

  • 对于 \(i < x + 1\)：对 \(R_i\) 无影响，对 \(L_i\) 的影响为：将 \(a_{x + 1}\) 在某些 \(R_i\) 中删除。

    \(R_i\) 被影响到 \(\iff\) \(\max\limits_{j = x + 1}^{i}a_j < a_{x + 1}\)。

  • 对于 \(i = x\) 和 \(i = x + 1\)：按原始方法处理。