P12389 COmPoUNdS

· · 题解

很好玩的一道题。

发现这个加操作很恶心，可以考虑差分。

如果没有取模的话就可以直接做了，但是有。如果你不是将相邻两数的差取绝对值来做，那么修改的中间部分可能会出现差的正负发生变化然后寄了。于是考虑取绝对值，然后手模几组发现是对的，考虑证明。

假设相邻的两个数分别是 x,x+d 或 x,x+d-p，现在我们要证明这不可能同时成立：

考虑反证法，有：

x+d<p\land x+d-p\ge0

则：

x<p-d\land p-d\le x

矛盾，故两式不可能同时成立，于是这题我们就可以用线段树维护哈希切掉了。