P13724 [GCPC 2024] Interference

物理可以非常有趣！ 昨天，你的老师讲解了干涉现象的原理：如果你有两列波，它们在整个波长范围内的高度会相加！ 因此，如果两列波都在波峰处，合成后的波峰会更高。 同样地，如果两列波都在水面以下的波谷处，合成后的波谷会更低。 从技术上讲，波的高度被称为振幅，两波峰之间的距离被称为波长。 :::align{center}  图 I.1：样例输入 2 中三列波的干涉效果。黑点表示合成波在各点的高度。 ::: 今天，你的物理老师描述了她即将进行的一个实验的设置。 她将在一维水槽中制造驻波。 由于她对物理元素的精确控制，所有波都具有精确控制的振幅，并且只会在给定长度的区间内产生。 每列波的波长始终为 $4$，且第一个正波峰总是在区间的第一个位置。 我们只在整数点上测量波的振幅。 例如，振幅为 $2$，长度为 $9$ 的一列波可以表示为 $\texttt{2\ 0\ -2\ 0\ 2\ 0\ -2\ 0\ 2}$。 如果某个点没有波，则振幅为 $0$。 你的任务是预测在给定位置处，考虑到之前所有产生的波后，合成波的高度。

输入包含： - 一行两个整数 $n$ 和 $w$（$1 \le n \le 4000$，$1 \le w \le 10^9$），分别表示操作数和水槽的宽度。 - 接下来 $n$ 行，每行是波的描述或预测任务： - “$\texttt{!}\ p\ \ell\ a$”，表示一列波的描述，起始位置为 $p$，长度为 $\ell$（$1 \le p, \ell \le w$），振幅为 $a$（$1 \le a \le 10^9$）。保证 $p+\ell-1 \le w$。 - “$\texttt{?}\ p$”，表示对位置 $p$（$1 \le p \le w$）的预测任务。 参见图 I.1 以部分可视化样例 2。

对于每个预测任务，输出一行一个整数，表示在所询问位置处，所有已描述波的合成波的高度。

由 ChatGPT 4.1 翻译