题解：AT_arc210_a [ARC210A] Always Increasing

细数繁星 · 2025-11-23 11:00:25 · 题解

更好的体验。

A - Always Increasing

题目传送门。

题目描述

有一个长度为 N 的正整数序列 \{A_N\}，有 Q 种操作，第 q 种操作给定 i_q 和 x_q，将 A_{i_q}\gets A_{i_q} + x_q。

要求任意时刻，序列 A 呈单调递增。请给出最小的 \sum A，满足要求。

思路

观察到操作的顺序是会影响结果的。

维护两个数组：B 和 C。

若 i_q\ge 2，则其会对位于 i_q-1 的操作产生影响，即在 i_q-1 上的 A 的值只要加上其加上的值减去 x_q 即可。因为要满足 A_{i_q} > A_{i_q-1}，而当 A_{i_q} \gets A_{i_q} + x_q，要前者小于 A_{i_q}+x_q，若 A_{i_{q}-1} 略大，会影响后面所有的值（因为题目要求单调递增）。所以想到此构造方法。

如果有多次操作，自然在 A 的构造上选择其中最大的即可满足所有操作。C_i 表示最大的修改值。

若 i_q=n，其不产生影响，忽略。

提交记录。