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

chenzhiyv · 2025-11-13 20:00:08 · 个人记录

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 ，二分分界点即可。