CF2176E Solution

Toorean · 2025-12-12 11:28:41 · 题解

给出 n 个元素，有值 a_i 以及代价 c_i。n 次操作，每次操作使某项 c_i\gets 0，该操作是永久的。定义一个一组元素的贡献为：每次选择一对相邻元素，以二者最小 c_i 删掉值更小的，删到只剩一个的最小代价和。你需要计算出，每次操作后的这一组元素的最小代价。

考虑没有 c_i \gets 0 操作，对于原序列如何最小化代价。

设最小的满足 \max\limits_{j<i} a_j <a_i 的 j 为 L_i，最大的满足 \max_{j>i}\limits a_j>a_i 的 j 为 R_i。注意到对于一个元素 \{a_i,c_i\}，其可删除的所有元素为 (L_i,R_i)，把这个开区间称作元素 i 的「管辖区间」。显然，可以用两遍 单调栈 求出。

为了最小化代价和，每个位置被管辖应保留代价尽量小的那一个。预处理出在没有进行 c_i\gets 0 操作前的所有位置花费的代价（即管辖者在此位置上的代价），设为 b_i。可以直接用 区间赋值的线段树 来实现。具体地，按照代价大到小赋值 j\in[L_i+1,R_i-1] 为 b_j\gets c_i，这样保证了每个位置取代价最小值。

显然，对于一组元素的贡献即为 \sum b_i。

现在考虑加入清零操作怎么做。注意到初始 c_i\ge 1，因此只要清零，一定使代价最小。于是令 j\in[L_{p_i}+1,R_{p_i}-1],b_i\gets 0 即可，用线段树统计全局和即可。