题解原文:
因为 hj≤hi<hkh_j \leq h_i < h_khj≤hi<hk,所以可以看作 hkh_khk 对 有一个 hjh_jhj 的贡献,进而 hkh_khk 对所有 hj<hkh_j<h_khj<hk 的 jjj 的都有一份贡献,所以考虑以高度为下标开一颗线段树,维护区间最大值。
但如果这样处理,若出现了前面的 hkh_khk 的贡献已被计算,但当前转移的 hi>hkh_i>h_khi>hk,那岂不是查询的结果多减了 hkh_khk 的贡献?
求教。