结论1：若干个区间的贡献只被两个区间限制
然后我们就只用考虑两个区间的贡献就好了，可以扫描右端点，然后用之前扫描过的与其匹配
比如现在线段为\([l,r]\)，确定\(l\)为左端点，现在找右端点。需要\([l_1,r_1],.s.t~l\in[l_1,r_1]\)，然后\(r_1\)为右端点。
也就是扫完\([l_1,r_1]\)是将\(r_1\)其放入\([l_1,r_1]\)线段树内，在\([l,r]\)时在线段树上走到\(l\)的位置，取内部的线段更新
再线段树内的很多线段如何快速找到最优值。
令\(S_i=S_{i-1}+A_i,T_i=T_{i-1}+i\times A_i\)，可以发现\(val(l,r)=T_r-T_{l-1}-(L-1)(S_r-S_{l-1})=-S_r(l-1)+T_r~~~~+(l-1)S_{l-1}-T_{l-1}\)
就线段树内套个李超树就完了
原文：https://www.cnblogs.com/Grice/p/12852913.html