首先,如果你写过P9058的话,应该会想到支配点对这个 trick,我们不妨将此题的套路搬到这套题上.
定义点对 \((i,j),a_i\le a_j\),当 \((i,j)\) 被支配当且仅当存在 \(i<k<j\) 满足 \(a_i\le a_k \le a_j\)。
相应的,一个有效的点对 \((i,j)\),其中 \(i\) 满足 \(i\) 最大且 \(a_i<a_j\)。
我们不妨证明这个结论:
反证法,有 \(a_{pre},a_i \le a_j\),其中 \(pre<i<j\) ,假设 \((pre,j)\) 为有效点对,
点对 \((pre,i)\) 的权值为 \(|a_i-a_{pre}|\),\((pre,j)\) 的权值为 \(a_j-a_{pre}\)。
在之前的证明中,需要满足 \((pre,i)\) 的权值 小于 \((pre,j)\) 的权值才能得证,但是这里却失效了,怎么办呢???
不妨沿着此思路,固定右端点 \(j\),挖掘在区间 \([1,i)\) 这个区间内更优秀的左端点 \(pre\) 所满足的性质。
如果 \(pre\) 这个左端点在区间 \([1,i)\) 中更加优秀,有:\(a_i<a_{pre}<a_j\) 且 \(a_{pre}-a_i>a_j-a_{pre}\),继续考虑在区间 \([1,pre)\) 区间内更加优秀的左端点 \(pre'\),有:\(a_{i}<a_{pre'}<a_{pre}\) 且 \(a_{pre'}-a_{pre}>a_j-a_{pre'}\)。
不妨简化下式子,得:\(2a_{pre}>a_i+a_j\),\(2a_{pre'}>a_{j}+a_{pre}\),发现左端点的权值是以指数级别增加的,那么对于一个右端点最多有 \(log_2V\) 个左端点。
如何实现?