算法竞赛之差分进阶——等差数列差分 python
前置知识
给定区间 [ 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)}')
如果有更多问题或需要进一步的帮助，可以在评论区留言讨论哦！
如果喜欢的话，请给博主点个关注 谢谢
原文地址：https://blog.csdn.net/2401_87245677/article/details/145292150
免责声明：本站文章内容转载自网络资源，如侵犯了原著者的合法权益，可联系本站删除。更多内容请关注自学内容网（zxcms.com）！