Luogu P4231【三步必杀】

· · 题解

传送门: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:(我知道有的人看这么久其实只想看这个)

#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;
}