CF1887D Split 题解-526互联

我现在水平好烂，再做下去自信心就全败没了
先考虑 \(Q=1\) 怎么做？
两种做法：
- 暴力枚举分界点，左右判断
- 暴力枚举 \(\max\limits_{i=l}^{x} a_i\)，找到最靠右边的分界点位置 \(x\)，判断是否 \(\max\limits_{i=l}^{x} a_i < \min\limits_{i=x+1}^{r} a_i\)
如果你选择优化第一个方法，因为暴力枚举分解点显然没有单调性，判断复杂度也不能整体考虑，因此考虑第二种做法的优化
暴力枚举依然没有优化空间，考虑后面这个问题如何整体算。
既然我们都枚举了最大值，肯定和极值的大小关系有关嘛。我们枚举 \(a_i\) 作为最大值，则记左边最近的 \(x\) 满足 \(a_x>a_i\)，记右边最近的 \(y\) 满足 \(a_i<a_y\)，记在 \(y\) 右边最近的 \(z\) 满足 \(a_i>a_z\)。则发现当 \(x<l \leq i\) 且 \(y \leq r < z\) 时 \([l,r]\) 满足条件。
我们把区间 \([l,r]\) 看成一个点，这显然就是一个矩形加单点查的问题。可以使用树状数组 \(+\) 扫描线解决
怎么求 \(x,y,z\)？没有要求线性，\(set\) 即可
单调栈应该不可做，因为 \(z\) 的限制不是 \(a_y > a_z\)
最终复杂度 \(O(n \log n)\)