当前位置：首页 > article >正文

算法竞赛之差分进阶——等差数列差分 python

article 2025/1/22 10:03:26

前置知识

给定区间 [ l, r ]，让我们把数组中的[ l, r ] 区间中的每一个数加上c,即 a[ l ] + c , a[ l + 1 ] + c , a[ l + 2] + c , a[ r ] + c;

怎么做？很简单，差分一下即可

还不会的小伙伴点此进入学习

进入正题

进阶一下：
给定区间 [ l, r ]，把数组[ l, r ] 区间中的数加上一个首项s、末项e、公差为d的等差数列,
即 a[ l ] + s , a[ l + 1 ] + s+d , a[ l + 2 ] + s+2d ······a[ r ] + e

怎么实现？先给出结论

a[l] += s，
a[l + 1] += d - s
a[r + 1] -=d + e
a[r + 2] += e
再对a数组做两次前缀和，即得到ans

为何？
下面听我娓娓道来~

简单举个例子：
假设数组a=【0，0，0，0，0，0，0，0】
现要求对 a[1] 到 a[5] 这5个数字分别加上以s为首项，d为公差，e为末项的等差数列，即a=【0，s，s+d，s+2d，s+3d，s+4d（e），0，0】
如何得到呢？我们先做一次差分试试：
diff1=【0，s，d，d，d，d，-e，0】什么也看不出来对吧。
再对差分数组做差分：
diff2=【0，s，d-s，0，0，0，-e-d，e】
哎，这不是一开始所进行的操作吗？
a[1]+=s
a[2]+=d-s
a[6]-=d+e
a[7]+=e
一切终成闭环

好了，实际运用的时候到了

实战演练

P4231 三步必杀 https://www.luogu.com.cn/problem/P4231

在这里插入图片描述

不了解异或运算可点此进入

题解code：

n, m = map(int, input().split())
ans = [0] * (n + 3)
for i in range(m):
    l, r, s, e = map(int, input().split())
    d = int((e - s) / (r - l))
    ans[l] += s
    ans[l + 1] += d - s
    ans[r + 1] -= d + e
    ans[r + 2] += e    # 实现等差数列差分

for i in range(1, len(ans)):
    ans[i] += ans[i - 1]
for i in range(1, len(ans)):
    ans[i] += ans[i - 1]   # 两次前缀和

xor = 0
for i in ans:
    xor ^= i
print(f'{xor} {max(ans)}')