P4231 三步必杀

题目
普及+/提高

思路

差分定义：

原序列中的该位置与上一位置之差，即：

$c_i=a_{i}-a_{i-1}$

---

由题知，伤害区间是一个等差数列，公差为$b=(e-s)/(r-l)$。

那么一次差分就可以把序列除了前两项和后面多出来的一项全部变成$b$。

要修改的还是太多了，观察这么多$b$，我们不如再差分一次。

那么再来一次差分不就可以把这些相邻的$b$全部变成$0$。

通过计算（自己模拟一下），我们得到最终这个序列只有四个数被修改，

即：

b=(e-s)/(r-l);
c[l]+=s;
c[l+1]+=b-s;
c[r+1]-=b+e;
c[r+2]+=e;

然后对它求两遍前缀和就可以了。

异或和记得初始值为$0$（$0$异或任何数都是它本身）。

代码

#include<bits/stdc++.h>
using namespace std;
const int N=1e7+7;
typedef long long ll;
int n,m;    
ll c[N];
int main()
{
    scanf("%d%d",&n,&m);
    for(int i=1;i<=m;i++)
    {
        int l,r,s,e;
        scanf("%d%d%d%d",&l,&r,&s,&e);
        c[l]+=s;//二次差分推导
        c[l+1]+=(e-s)/(r-l)-s;
        c[r+1]-=(e-s)/(r-l)+e;
        c[r+2]+=e;
    }
    ll ans1=-1,ans2=0,a=0,b=0;//最大值，异或和，二次前缀和，一次前缀和
    for(int i=1;i<=n;i++) 
    {
        b+=c[i];
        a+=b;
        ans1=max(ans1,a);
        ans2^=a;
    }
    printf("%lld %lld",ans2,ans1);
    return 0;
}