题解 P3655 【不成熟的梦想家 (未熟DREAMER)】

# 洛谷三月月赛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的解法。 今天看到有很多人用奇奇怪怪的做法水过，各种树状数组等。 #### 本题标程请见题目页面下方的标程部分。