题解 P4231 【三步必杀】

· · 题解

我们来分数据范围看看做法:

首先是1<=n,m<=1000

暴力模拟即可，不必多说。

然后是s=e。这意味着题目变成多次区间加，然后询问。那么利用差分即可解决。

l.......... r+1

s..........-s

这时求前缀和，相当于给[l,r]中的每个数字都增加了s。

接下来看看正解，顺便也解决1<=n<=1e5,1<=m<=1e5的情况。

因为是等差数列，所以我们还是利用差分。

经过一次差分，我们发现对于一个l,r,s,e操作,先求出公差d,然后可以变成这样:

l l+1 l+2.......r r+1

s d d .......d -s-(r-l)*d

就变成了两次单点加和一次区间加了。那么怎么办呢？

可以用树状数组/线段树来维护区间,每次操作O(logn),这就是1e5的做法了。

那么正解呢？再差分一次就好(应该没人想到这一步还想不到正解吧)。

l l+1 .......... r+1 r+2

s d-s -(r-l+1)d-s s+(r-l)d

最后求两次前缀和就能获得原数组了。

这样每次操作是O(1)的,总复杂度O(n+m),顺利通过。

后续剧情

（四）三步必杀

荷取不断地思考着.... "让我看看，每次产生的伤害都是一个等差数列？"

"等差数列嘛.....似乎看不出什么玄机呢。"

"但是，如果不是等差数列，而是对每一个柱子产生的伤害相同，情况可能会不一样。"

"如果对每个柱子产生的伤害相同，我只要记录下伤害开始和结束的位置就可以了" "具体怎么样呢..."

"嗯，把柱子从左到右编号 1,2,3...,伤害开始的地方记做 L，结束的地方记做 R。 在 L 这里记一个 1，就表示从现在开始，往右边的柱子都受到了 1 的伤害。

但是这么做的话，在 R 右侧的柱子受到的伤害就会凭空多出 1。

那么，只要在 R 右边的那个柱子标记一个-1，就可以抵消掉了。

而且这样的标记是独立的，可以累加! "

"这样的话，每次攻击我只需要在一个临时序列 S 上改两个数字，等到最后从左到右求 一遍和就可以得到结果了

这个 S 序列通过一次记录两个数，得到了每次伤害对其之后柱子损伤程度的影响 由于用到做差与求和，那我就先把这个 S 叫差分序列，从左到右求和后的序列叫前缀 和序列吧。

嗯，很不错呢，很不错呢。"

荷取的眼睛闪着光芒。

"可真正的伤害不是固定的，是一个等差数列啊，那怎么办。" 巨响不断，荷取有些失落，但依然在敲着键盘。

围观的鬼们显得有些疲惫了，为了让荷取记录下这些伤害信息，每两轮攻击之间都要等好久。

但是，没有一只鬼在抱怨。

"等等，等差？"

...

...

... "这不就是固定了伤害的增量?" 荷取仿佛看到了希望。

"那样的话，之前应对固定伤害的办法或许就有用了。"

"只要用另一个 A 序列记录下伤害的增量对其之后伤害的影响就可以了。

对 A 序列求前缀和，就可以得到刚才的那个 S 序列。

那么，这个 A 序列可以说是差分序列的差分序列。"

"对了，除了考虑增量还要考虑初始值，那么用 B 序列记录初始伤害和结束伤害，最后 加进 S 序列就行。"

"这个问题好像解决了?"

... 妖怪之山，山脚下。

荷取和同伴正在瀑布边玩耍。

虽然已经入夜，但距离深夜还早，荷取的愿望实现了。

啊不过，时间真的不早了，我们的地底旅行还要继续。

咦，这个方法，不正好可以用来解决山女的连环病原体难题吗？

真是意外的收获呢，回去的时候记得告诉山女~ 那么,接下来是，地灵殿?