P10173 「OICon-02」maxiMINImax

P10173 「OICon-02」maxiMINImax

首先观察所求的式子，我们可以很容易发现 \(\min_{[l_2,l_2]}>\max(\max_{[l_1,r_1]},\max_{[l_3,r_3]})\)，否则贡献一定为 \(0\)。

此时如果要考虑枚举其中一个区间，我们肯定选择中间的 \([l_2,r_2]\)，但是这样复杂度仍然至少是 \(O(n^2)\)。

我们思考是否真的需要枚举区间。枚举区间的意义是能够知道 \([l_1,r_1]\) 和 \([l_3,r_3]\) 的区间范围，达到题目条件中的三个区间不交。但是我们发现，假如 \([l_2,r_2]\) 与 \([l_1,r_1]\) 相交，那么在相交区间内一定存在一个位置 \(p\)，使得 \(\min_{[l_2,r_2]}\le a_p\le \max_{[l_1,r_1]}\)，无法满足第一个条件。

此时我们知道，只需要满足 \(\min_{[l_2,l_2]}>\max(\max_{[l_1,r_1]},\max_{[l_3,r_3]})\)，区间一定不交。

考虑计算贡献，我们容易用单调栈预处理出每个位置作为最大值/最小值的区间数 \(c_i/d_i\)。

此时枚举 \(a_i\) 作为 \(\min_{[l_2,l_2]}\)，所有位置的答案即为 \(\sum c_{min2}d_{max1}d_{max3}(min2-max1)(min2-max3)\)。

如何维护这个东西？考虑拆开式子，发现只需要维护 \(\sum c\)，\(\sum d\)，\(\sum cmax\)，\(\sum dmax\)。

我们在计算时要满足第一个条件，这里用一个技巧，就是把数从小到大放进去同时维护树状数组即可，当然也可以用权值线段树分别维护前缀和后缀。

复杂度 \(O(n\log n)\)。