关键词: 差分  二阶差分  数据结构-链表 相关题目:  三步必杀

题目描述

    NN个柱子排成一排,一开始每个柱子损伤度为0。接下来会进行MM次攻击,每次攻击可以用4个参数 llrrssee 来描述:     表示这次攻击作用范围为第 ll 个到第 rr 个之间所有的柱子(包含 ll , rr ),对第一个柱子的伤害为 ss ,对最后一个柱子的伤害为 ee 。     攻击产生的伤害值是一个等差数列。若 l=1,r=5,s=2,e=10l=1 ,r=5 ,s=2 ,e=10 ,则对第1~5个柱子分别产生2,4,6,8,102,4,6,8,10的伤害。     需要计算的是所有攻击完成之后每个柱子的损伤度。

输入输出格式

输入格式:     第一行2个整数 NN , MM ,用空格隔开,下同。     接下来 MM 行,每行4个整数 ll , rr , ss , ee ,含义见题目描述。     数据保证对每个柱子产生的每次伤害值都是整数。

输出格式:     由于输出数据可能过大无法全部输出,为了确保你真的能维护所有柱子的损伤度,只要输出它们的异或和与最大值即可。(异或和就是所有数字按位异或起来的值)

数据规模

    对于全部的数据: 。     所有输入输出数据以及柱子受损伤程度始终在 [0,9×1018][0,9\times 10^{18}] 范围内。

解决方案:

    注意到每次操作是区间修改,修改值为等差数列,很自然的第一想法是用线段树维护差分值。时间复杂度 Θ((m+n)log(n))((m+n)log(n)) 有点问题...... 有没有 Θ(m+n)(m+n) 的做法??朝这一方面想,结合等差数列(好像没关系的诶)那么就很容易想到差分了。然后㖏,对于这道题目,我们可以只差分一次,用二阶差分的办法去做。

    对于每一次修改的操作,时间复杂度必须为 Θ(1)(1) ,那么我们可以用链表储存单点的值。假设一次对于区间 [l,r][l,r] 值为 ssrr 的修改。我们在节点 ss 储存这次的差分值(即公差 dd ),还要储存节点值 ss ,然后在 s+1s+1 处恢复差分值(即节点值储存 d-d ),恢复节点 ss 的差分值影响(即储存 ed-e-d )。那么对于差分值查询只需要从节点 11nn 依次节点储存值累加就好了,若该点为节点,再加上节点的储存值即可。好了好了好了吧,上代码。

AC代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
#include<cstdio>
#define re register int
#define rep(i,a,b) for(re i=(a);i<=(b);++i)
#define max(a,b) ((a)>(b)?(a):(b))
#define N 10000020
typedef long long ll;
struct node{
int nxt;
ll k,z;
}t[600020];

int n,m,l,r,cnt=0;
ll s,e,d,maxn=0,head[N];
ll p[2];

inline void add(int num,ll k,ll z){
t[++cnt].nxt=head[num];
head[num]=cnt;
t[cnt].k=k;//端点值
t[cnt].z=z;//公差
}//链表储存

int main(){
scanf("%d%d",&n,&m);
while(m--){
scanf("%d%d%lld%lld",&l,&r,&s,&e);
d=(e-s)/(r-l);
add(l,s,d);
add(r+1,-e-d,-d);
}

ll ans=0,sum=0;
int cur,sk;

rep(i,1,n){
cur=i&1,sk=!cur;
p[cur]=p[sk]+sum;
for(re j=head[i];j;j=t[j].nxt){
sum+=t[j].z;
p[cur]+=t[j].k;
}
maxn=max(maxn,p[cur]);
ans^=p[cur];
}
printf("%lld %lld\n",ans,maxn);
return 0;
}