「Luogu P4231」三步必杀 解题报告

题面

长度为 $n$ 的序列，$m$ 次修改，每次修改，令 $[l,r]$ 区间加上首项为 $a$，末项为 $b$ 的等差数列

$1\le n\leq10^7,1\le m\le3\times 10^5,1\le l< r\le n.​$

解题思路

前缀和

分析

如果你不怕 $T$ 上天，可以用线段树维护，获得 $O(n\log n)$ 的优秀复杂度

等差数列的性质能让人联想到等差数列，考虑确实是这样的，

可以通过两个数组，分别维护首项和单位上升的大小

单位上升的大小即为等差数列的公差

这样只用最后扫一遍得出前缀和即可，时间复杂度 $O(n+m)$ （m<< n 可以不用考虑

warning

1、维护公差的数组要从 $l+1$ 的位置开始修改

2、维护首项的数组 $r+1$ 的位置要减 $b​$，这样才能抵消前面产生的影响

code

#include<bits/stdc++.h>
#define rgt register
#define rint rgt int
#define LL long long
#define rll rgt LL
#define inf 0x7f7f7f7f
#define N 10000007
using namespace std;
template<class K>inline bool cmax(K&a,const K&b){return(a<b)?a=b,1:0;}
template<class K>inline bool cmin(K&a,const K&b){return(a>b)?a=b,1:0;}
template<class K>inline void read(K&s) {
    s=0;rgt char c=getchar();
    while(!isdigit(c)) c=getchar();
    while(isdigit(c)) s=(s<<1)+(s<<3)+c-'0',c=getchar();
}
int n,T;LL s[N],f[N],ans,res,a,b;
int main()
{
    rint i,l,r;read(n),read(T);
    while(T--) {
        read(l),read(r),read(a),read(b);//s[_]表示首项的前缀和，注意r+1减的是b
        s[l]+=a,f[l+1]+=(b-a)/(r-l),s[r+1]-=b,f[r+1]-=(b-a)/(r-l);
    }//f[_]维护的是公差的前缀和
    for(i=1;i<=n;i++) f[i]+=f[i-1],s[i]+=s[i-1]+f[i],ans^=s[i],cmax(res,s[i]);
    printf("%lld %lld",ans,res);
    return 0;
}