题目内容

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;
}
最后修改日期:2020年3月29日

作者

留言

撰写回覆或留言

发布留言必须填写的电子邮件地址不会公开。