题目描述

N个柱子排成一排，一开始每个柱子损伤度为0。

接下来勇仪会进行M次攻击，每次攻击可以用4个参数l,r,s,e来描述：

表示这次攻击作用范围为第l个到第r个之间所有的柱子(包含l,r)，对第一个柱子的伤害为s，对最后一个柱子的伤害为e。

攻击产生的伤害值是一个等差数列。若l=1,r=5,s=2,e=10，则对第1~5个柱子分别产生2,4,6,8,10的伤害。

鬼族们需要的是所有攻击完成之后每个柱子的损伤度。

原题链接

Solve

如果是区间内都增加一个相同的数值的话，那这个题就很显然了，树状数组、线段树和差分数组都可以秒切，但是此题增加的是一个等差数列，那我们怎么做呢？

1，暴力?每次询问都从l到r扫个遍？想想都不行。

2，差分？树状数组？线段树？又好像跟我们认识的不太一样。

所以，就让我们打开新世界的大门，认识差分的另一面。

普通的差分数组：

而联系上等差序列呢？

当然$b_1$不一定等于公差。看完了之后有什么想法吗？

如果我们在差分一次呢？我们叫他二阶差分。

通化一点

s为首项，e为尾项，d为公差

a关于b差分，如同b关于c差分

于是我们成功的将区间加转变为了单点加，复杂度呜呜地减。

最后一次还原就好啦。

Tip

莫得忘了开long long

Code

#include<iostream>
#include<cstdio>
#include<cstring>
#define N 10000001
#define ll long long
using namespace std;
ll n,m;
ll l,r,s,e;
ll ans1,ans2;
ll a[N],b[N],c[N];
inline ll read(){
    ll x=0,f=1;
    char ch=getchar();
    while(ch<'0'||ch>'9'){
        if(ch=='-') f=-1;
        ch=getchar();
    }
    while(ch>='0'&&ch<='9'){
        x=(x<<1)+(x<<3)+(ch^48);
        ch=getchar();
    }
    return x*f;
}
int main()
{
	n=read();m=read();
	for(ll i=1;i<=m;i++){
		l=read();r=read();s=read();e=read();
		ll d=(e-s)/(r-l);
		c[l]+=s;
		c[l+1]+=(d-s);
		c[r+1]+=(-e-d);
		c[r+2]+=e;
	}
	for(ll i=1;i<=n;i++){
		b[i]=c[i]+b[i-1];
		a[i]=b[i]+a[i-1];
		ans1^=a[i];
		ans2=max(ans2,a[i]);
	}
	printf("%lld %lld",ans1,ans2);
	return 0;
}