容易先处理出 $L(a)$ 和 $R(a)$，设元素个数分别为 $cntL,cntR$。
接下来考虑 DP。设 $dp1_{i,j}$ 表示前 $i$ 个数选了 $L$ 中的前 $j$ 个数的方案；$dp2_{i,j}$ 表示后 $i$ 个数选了 $R$ 中的前 $j$ 个数的方案。两者方程相似，故下面只对 $dp1$ 进行讲解。
考虑转移，对于当前的数 $a_i$，以及 $L$ 的前 $j$ 个数已经被选择，可以分为以下三种情况：
$a_i = L_j$ 若 $L_j$ 在之前已经被选择，则 $a_i$ 选不选均可，否则需要强制选，则有转移 $dp_{i,j} = 2dp_{i - 1,j} + dp_{i - 1,j - 1}$。
$a_i < L_j$ $a_i$ 的选择不会对 $L^\prime$ 造成影响，则有转移 $dp_{i,j} = 2dp_{i - 1,j}$。
$a_i > L_j$ 不能选择 $a_i$，否则会破坏 $L = L^\prime$，则有转移 $dp_{i,j} = dp_{i - 1,j}$。
当统计答案时，需要小心重复计算的情况。因此当 $a_i$ 为全局最大值时，强制让 $dp1$ 去选择这个最大值，然后强制 $dp_2$ 不选这个最大值，则对答案的贡献为 $(dp1_{i,cntL} - dp1_{i - 1,cntL}) \times dp2_{i + 1,cntR - 1}$。
时间复杂度为 $O(n^2)$，代码如下：
1 | void solve () |
容易先处理出 $L(a)$ 和 $R(a)$，设元素个数分别为 $cntL,cntR$。
接下来考虑 DP。设 $dp1_{i,j}$ 表示前 $i$ 个数选了 $L$ 中的前 $j$ 个数的方案；$dp2_{i,j}$ 表示后 $i$ 个数选了 $R$ 中的前 $j$ 个数的方案。两者方程相似，故下面只对 $dp1$ 进行讲解。
考虑转移，对于当前的数 $a_i$，以及 $L$ 的前 $j$ 个数已经被选择，可以分为以下三种情况：
$a_i = L_j$ 若 $L_j$ 在之前已经被选择，则 $a_i$ 选不选均可，否则需要强制选，则有转移 $dp_{i,j} = 2dp_{i - 1,j} + dp_{i - 1,j - 1}$。
$a_i < L_j$ $a_i$ 的选择不会对 $L^\prime$ 造成影响，则有转移 $dp_{i,j} = 2dp_{i - 1,j}$。
$a_i > L_j$ 不能选择 $a_i$，否则会破坏 $L = L^\prime$，则有转移 $dp_{i,j} = dp_{i - 1,j}$。
当统计答案时，需要小心重复计算的情况。因此当 $a_i$ 为全局最大值时，强制让 $dp1$ 去选择这个最大值，然后强制 $dp_2$ 不选这个最大值，则对答案的贡献为 $(dp1_{i,cntL} - dp1_{i - 1,cntL}) \times dp2_{i + 1,cntR - 1}$。
时间复杂度为 $O(n^2)$，代码如下：
1 | void solve () |
首先在 E1 的基础上可以滚动数组优化。其次，再次观察可以发现，每次的转移其实只是可根据与 $a_i$ 的相对大小从而分为三类。
首先用 lower_bound 找到满足 $L_x \ge a_i$ 这一条件最小的 $x$。若能够取等，则这一单点相当于可以从 $x$ 和 $x - 1$ 两个单点转移而来。对于 $L_x > a_i$ 的，相当于进行区间乘 $2$ 的操作；对于 $L_x < a_i$ 的，相当于继承原有的值，不做任何处理即可。最后的答案，显然只需要将 $cntL$ 与 $cntR - 1$ 时候的值存下来，单点查询就能满足。
因此需要用能够实现区间乘，单点加，单点查询的数据结构维护，直接上线段树即可。时间复杂度优化为 $O(n \log n)$。
代码如下：
1 |
|
