解题报告 P4231 三步必杀

题目内容

P4231

大意：区间加等差，最后询问整个序列的异或和以及最大值

解题思路

区间加等差其实就是差分序列区间加常数，两端特殊修改。

但是注意到这里的数据范围是 1e7，线段树卡不过去，而且询问是在最后询问的，因此可以直接上二阶差分。

模拟一段区间加等差的过程：给 [3,6] 加上首项为 3，末项为 9 的等差数列：

0  0  0  0  0  0  0  0  这是原数列
0  0  3  5  7  9  0  0  这是加了等差数列之后的
0  0  3  2  2  2 -9  0  这是一阶差分
0  0  3 -1  0  0  -11 9 这是二阶差分

可见，我们如果要进行区间加等差的操作的话，需要在二阶差分上动 4 个点，分别是

d2[l]+=s;
d2[l+1]+=d-s;
d2[r+1]-=e+d;
d2[r+2]+=e;

其中 d 为公差，s 为首项，e 为末项。错误常发生于以为 d2[l+1] 和 d2[r+1] 是不用修改的，但是实际上由于 s 可能不等于 d，故二阶差分的 l+1 处要进行处理。

最后，两次前缀和就可以还原出原序列，在还原的过程中可以顺便进行最大值查询和异或和操作。

总的复杂度 O(n+m)，可以卡过去，如果是线段树的话是 O(m\log n+n)，会被卡掉

要开 long long

#include <cstdio>
#include <cctype>
typedef long long ll;

const int maxn=1e7+5;
ll a[maxn],d1[maxn],d2[maxn];

inline ll read()
{
    char c = getchar();
    ll s = 0;
    while (!isdigit(c))
        c = getchar();
    while (isdigit(c))
        s = 10 * s + c - '0', c = getchar();
    return s;
}

int main()
{
    int n=read(),m=read();
    ll l,r,s,e;
    while(m--)
    {
        l=read(),r=read(),s=read(),e=read();
        int d=(e-s)/(r-l);//得到公差
        d2[l]+=s;
        d2[l+1]+=d-s;
        d2[r+1]-=e+d;
        d2[r+2]+=e;
    }
    ll maxans=0,ans=0;
    for(int i=1;i<=n;i++)
    {
        d1[i]=d1[i-1]+d2[i],a[i]=a[i-1]+d1[i];//还原
        maxans=maxans<a[i]?a[i]:maxans;
        ans^=a[i];
    }
    printf("%lld %lld\n",ans,maxans);
    return 0;
}