算是 差分 的进阶吧,这道题算是差分+差分的题目,即要两次差分再求前缀和。
先来解释原理:
给定一个数组a长度为n,初始都为0。接下来m个操作:
1、在l~r的范围上加上一个首项为s,末项为e的等差数列。
接着求出m次操作后数组a的各项值
例如【0,0,0,0,0,0,0,0,0,0】的数组
一次操作为在4~8的位置上加上首项为4,末项为16的等差数列。
看着像差分,但细想又不太一样,因为我们进行前缀和操作之前的数组a应该如下
【0,0,0,4,3,3,3,3,-16,0】,l~r位置上的值都变了,导致只用一次差分无法解决。
那么我们在观察一下发现上面这个数组可以根据【0,0,0,4,-1,0,0,0,-19,16】通过前缀和求得。
那么我们就可以通过一次差分+两次前缀和的方式来实现对数组的转化。
主要代码:
#include<bits/stdc++.h> using namespace std; const int N=1e7+5,M=3e5+5; typedef long long ll; ll a[N]; int l[M],r[M],s[M],e[M]; int n,m; ll max_=0,pre=0; void setbuild(){ for (int i=1;i<=m;i++){ int d=(e[i]-s[i])/(r[i]-l[i]); a[l[i]]+=s[i]; a[l[i]+1]+=d-s[i]; a[r[i]+1]-=d+e[i]; a[r[i]+2]+=e[i]; } } void build(){ for (int i=1;i<=n;i++) a[i]+=a[i-1]; for (int i=1;i<=n;i++){ a[i]+=a[i-1]; max_=max(max_,a[i]); pre^=a[i]; } } int main(){ ios::sync_with_stdio(false); //由于输入量巨大,不加这一句会超时 cin>>n>>m; for (int i=1;i<=m;i++) cin>>l[i]>>r[i]>>s[i]>>e[i]; setbuild(); build(); cout<<pre<<" "<<max_; return 0; }
标签:前缀,16,int,ll,必杀,差分,P4231,数组,三步 From: https://www.cnblogs.com/purple123/p/18003430