20251113【NOIP】模拟 B. 序列 (seq)

20251113【NOIP】模拟 B. 序列 (seq)

首先，对原序列建出大根笛卡尔树，对于每一个节点，考虑左右儿子与这个点的贡献，维护左右儿子的 $\sum x_i,a_i,cnt$ ，即总共的 $x_i$ 的和，$a_i$ 的值，注意为了不使这个加法无效，必须一段一起加，贡献为 $2*k*\sum x + k^2*cnt$，原来的代价是 $(a_i-a_{ls/rs})*c$ ，二分分界点即可。