一个对题解的疑问
查看原帖
一个对题解的疑问
368124
Aurora_Borealis_楼主2023/5/13 23:21

题解原文:

因为 hj≤hi<hkh_j \leq h_i < h_k,所以可以看作 hkh_k 对 有一个 hjh_j 的贡献,进而 hkh_k 对所有 hj<hkh_j<h_k 的 jj 的都有一份贡献,所以考虑以高度为下标开一颗线段树,维护区间最大值。

但如果这样处理,若出现了前面的 hkh_k 的贡献已被计算,但当前转移的 hi>hkh_i>h_k,那岂不是查询的结果多减了 hkh_k 的贡献?

求教。

2023/5/13 23:21
加载中...