这个方法的核心做用是:
将不满足可减性的求值,变成只需要可以区间拼合(即满足区间可加性)的求值式子.
这个式子当然还是是 \(O(n^2)\) 的,但是常常它比原问题的那个更加的简便,有无穷的威力.简便在哪?简便在于,本来这个式子可能不满足区间可减性,但是经过这样的分治,它只需要区间可加就行了,于是可以转化为第 II 节中的方法.
利用上述转化后问题就变成了可以用第 II 部分中的第一种处理,设 \(g(i)\) 为前缀/后缀最大值,那么它一定是单调的,即对于每一个位置的最大值的贡献,我就看一下另一边有多少个数小于它即可.尺取法一下复杂度 \(n\log n\).事实上还有很多其他解法,这里只是作为一个 example.