Luogu P4231【三步必杀】

传送门:[P4231](https://www.luogu.org/problemnew/show/P4231) 差分好题。 由于增加的是等差数列，所以可求相邻两项的差。将差设为$d$，则$d=\frac{e-s}{r-l}$。因为题目保证$l<r$，所以不用担心分母为$0$导致浮点错误。 接下来设原数组为$a$，差分数组为$b$。以$l=2,r=5,s=2,e=17$为例，数组$a,b$的变化如下： ``` i 1 2 3 4 5 6 7 ... a 0 2 7 12 17 0 0 ... b 0 2 5 5 5 -17 0 ... ``` 可以发现，每次修改转化成了$2$次单点加和$1$次区间加，可以用线段树维护，时间复杂度$O(n\log n+m\log n)$。 其实到这里已经距离正解很近了。通过差分的特性，我们可以发现：$1$单点修改进行差分会变成$2$次单点修改，而$1$次区间修改会被缩减成$1$次单点修改。尝试对$b$差分，差分数组记为$c$， ``` i 1 2 3 4 5 6 7 ... a 0 2 7 12 17 0 0 ... b 0 2 5 5 5 -17 0 ... c 0 2 3 0 0 -22 17 ... ``` 可以发现，原先的$2$次单点加和$1$次区间加，转化为了$4$次单点加！ 那么如何通过$c$来求出$a_i$呢？ 通过差分的定义，可以知道$a_x=\sum_{i=1}^{x}b_i$。又因为$c$是$b$的差分数组，所以$a_x=\sum_{i=1}^{x}\sum_{j=1}^{i}c_i$。 容易发现$\sum_{j=1}^{i}c_i$可以用前缀和优化掉(记为$s_i$)。问题转化为求$\sum_{i=1}^{x}s_i$，易得$a_i=a_{i-1}+s_i$，于是我们就可以愉快地在$O(n)$时间内求出变更完的$a$数组！ 现在探究一下修改操作的一般情况，对于每次修改操作，都有如下变化： ``` i l-1 l l+1 l+2 ... r-1 r r+1 r+2 ... a 0 s s+d s+2d ... e-d e 0 0 ... b 0 s d d ... d d -e 0 ... c 0 s d-s 0 ... 0 0 -e-d e ... ``` 所以对于每次修改$(l,r,s,e)$，我们只需要$c_l+=s,\ c_{l+1}+= (d-s)\ c_{r+1}+=(-e-d),c_{r+2}+=e$即可。 最后统计答案时对数组$c$参照前文过程$O(n)$扫一遍即可。 总时间复杂度：$O(n+m)$。 注意值域$[0,9\times10^{18}]$要开`long long`。 Code:~~(我知道有的人看这么久其实只想看这个)~~ ```cpp #include<bits/stdc++.h> using namespace std; inline long long fi() { register long long x=0;register char ch; while(!isdigit(ch=getchar()));x=ch-48; while(isdigit(ch=getchar()))x=x*10+ch-48; return x; } long long n,m,l,r,s,e,d; long long b[10000005]; int main() { n=fi();m=fi(); while(m--) { l=fi();r=fi();s=fi();e=fi(); d=(e-s)/(r-l); b[l]+=s; b[l+1]+=(d-s); b[r+1]+=(-e-d); b[r+2]+=e; } register long long ans1=0,ans2=0,tmp=0; for(register int i=1;i<=n;++i)b[i]+=b[i-1]; for(register int i=1;i<=n;++i) { tmp+=b[i]; ans1^=tmp; ans2=max(ans2,tmp); } cout<<ans1<<" "<<ans2; return 0; } ```