自动搬运

查看原文

来自洛谷，原作者为

	lin_toto Luscious Lawless

搬运于2025-08-24 21:51:17，当前版本为作者最后更新于2017-03-13 00:13:45，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

洛谷三月月赛R1·官方题解 T3

本题标程请见题目页面下方的标程部分。

1. 解析

本题的正解是O(n)算法。每次对于一个区间的唱功值的改变，不会导致区间内的值相对大小的改变。

因此对于B值，我们每次只需要维护X、Y两个节点上的变更就好了。

我本人的做法是预处理出f[i] = A[i]-A[i-1]，并通过f数组计算出初始的B值，每次在区间上增加Z的时候，先撤销之前f[X]和f[Y]对B值的贡献，计算出新的f[X]和f[Y]，然后同时更新B值。

2. 出题事故

本来应该70分给20万的数据，100分给100万。

结果因为一些出题组沟通上的问题，变成了并没有卡n*logn的解法。

今天看到有很多人用奇奇怪怪的做法水过，各种树状数组等。

本题标程请见题目页面下方的标程部分。