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\)：按原始方法处理。
-