不难发现序列 $a$ 的权值就是所有长度为 $3$ 的子区间的中位数的最大值。

直接记录 $a_i,a_{i-1}$ 的值和最大值，会有个 $O(nV^4)$ 的做法。

考虑枚举 $x$，计算有 $c_x$ 个权值 $\ge x$ 的序列，答案即为 $\sum c_x$。

固定 $x$ 之后之前的 dp 中记录每一位的值和最大值的维度都可以改为 $0/1$ 表示 $\ge x/

每个位置的转移取决于 $x,l_i,r_i$ 的大小关系，可以把 $x$ 由 $l_i,r_i$ 分成 $O(n)$ 段，这一段的 $x$ dp 过程是类似的，每个位置的转移时的系数都是只有乘常数，乘 $(ax+b)$ 两种可能。可以直接维护多项式，这样只需要 $O(n^2)$ 一次 dp 得到这个区间的多项式。然后要求出 $\sum_{i=L}^R F(i)=\sum_{i=L}^R \sum_{j=0}^n i^j f_j=\sum_{j=0}^nf_j\sum_{i=L}^Ri^j$。拉插求 $k$ 次幂和即可。复杂度 $O(n^3)$。