CF360A Levko and Array Recovery

Levko 非常喜欢由整数构成的数组 $a_{1},a_{2},\ldots,a_{n}$。因此，Levko 总是对数组 $a$ 进行各种操作。每次操作属于以下两种类型之一： 1. 将从 $l_{i}$ 到 $r_{i}$ 的所有元素加上 $d_{i}$。换句话说，对于所有满足 $l_{i} \leq j \leq r_{i}$ 的 $j$，执行 $a_{j}=a_{j}+d_{i}$。 2. 查询从 $l_{i}$ 到 $r_{i}$ 的元素的最大值。即计算值 \[ \max_{l_{i} \leq j \leq r_{i}}{a_{j}} \] 可惜的是，Levko 最近弄丢了他的数组。幸运的是，他保留了自己对数组 $a$ 的全部操作记录。请你根据操作记录，帮Levko 找出至少一个满足条件的原始数组，并保证对于给定的操作记录，所有操作的结果都完全吻合。同时，Levko 清楚地记得，数组中的所有元素的绝对值都不超过 $10^{9}$，请你找出这样一个数组。

第一行包含两个整数 $n$ 和 $m$（$1 \leq n, m \leq 5000$），分别表示数组的大小和Levko 操作的数量。 接下来 $m$ 行，每行描述一个操作，第 $i$ 行描述第 $i$ 次操作。每行第一个整数为 $t_{i}$（$1 \leq t_{i} \leq 2$），表示操作类型。如果 $t_{i}=1$，则后面跟着三个整数 $l_{i}$、$r_{i}$ 和 $d_{i}$（$1 \leq l_{i} \leq r_{i} \leq n$，$-10^4 \leq d_{i} \leq 10^4$），表示第一类操作。如果 $t_{i}=2$，则后面跟着三个整数 $l_{i}$、$r_{i}$ 和 $m_{i}$（$1 \leq l_{i} \leq r_{i} \leq n$，$-5 \cdot 10^7 \leq m_{i} \leq 5 \cdot 10^7$），表示第二类操作。 操作按照Levko 执行的顺序给出。

第一行输出 “YES”，如果存在满足条件的数组，否则输出 “NO”。 如果存在解，则第二行输出 $n$ 个整数 $a_{1},a_{2},\ldots,a_{n}$（$|a_{i}| \leq 10^{9}$），表示还原出的原始数组。

由 ChatGPT 5 翻译