本期主要讲解差分技巧。
知识点
我们令原数组为 \(a_i\)，则当且仅当 \(d_i=a_i-a_{i-1}\) 时，我们称 \(d_i\) 是 \(a_i\) 的差分数组。
特别的，\(d_1=0\)，\(d_{n+1}=-n\)。
差分数组 \(d_i\) 有以下三个性质：
-
\(d_i\) 的前缀和数组为 \(a_i\)。
-
将 \(a_{L \sim R}\) 这个区间统一加上 \(val\)，等价于 \(d_L \gets d_L+val\) 且 \(d_{R+1} \gets d_{R+1}-val\)。
-
\(\sum^{n}_{i=1} d_i = 0\)。
例题
T1
板子题，放下代码供以后复习用。
#include<bits/stdc++.h>
using namespace std;
int n,p,ans=1e9+31;
int a[5000031],d[5000031];
int main(){
cin>>n>>p;
for(int i=1;i<=n;i++) cin>>a[i],d[i]=a[i]-a[i-1];
while(p--){
int x,y,z; cin>>x>>y>>z;
d[x]+=z,d[y+1]-=z;
}
for(int i=1;i<=n;i++) a[i]=a[i-1]+d[i];
for(int i=1;i<=n;i++) ans=min(ans,a[i]);
cout<<ans;
return 0;
}
T2
有意思的结论题。
根据差分数组的性质二，我们知道 将 \(a_{L \sim R}\) 这个区间统一减少 \(1\)，等价于 \(d_L \gets d_L-1\) 且 \(d_{R+1} \gets d_{R+1}+1\)。
而根据性质三，我们又知道 \(\sum^{n}_{i=1} d_i = 0\)，这就说明差分数组中的正负数可以互相抵消。
因此，我们可以求出差分数组，再一正一负地进行对原数组的区间操作，这样每次操作后差分数组的正数和会 \(-1\)，而负数和会 \(+1\)。
若我们令差分数组的正数和为 \(S_1\)，那么要让原数组变为全 \(0\)（也就是差分数组变为全 \(0\)），显然需要 \(S_1\) 次操作。
所以，我们仅需求出 \(S_1\) 即为答案。
#include<bits/stdc++.h>
using namespace std;
long long n,a[100031],d[100031],sum;
int main(){
cin>>n;
for(int i=1;i<=n;i++){
cin>>a[i],d[i]=a[i]-a[i-1];
if(d[i]>0) sum+=d[i];
}
cout<<sum;
return 0;
}
T3
对于一段铁路，我们仅能买票或者买卡，因此若第 \(i\) 段铁路经过的次数为 \(x\)，则对于这一段铁路的最小花费为：
\[\min(a_i \times x,b_i \times x + c_i) \]观察上式，\(a_i,b_i,c_i\) 我们都是已知的，因此影响铁路最小花费的因素只有其经过的次数。问题转变为了如何统计每一段铁路被经过的次数。
很容易想到对于 \(m\) 次旅程依次枚举累加，但会 \(\color{navy}{\texttt{TLE}}\)。
于是我们想到对于第 \(i\) 次旅程都是将 \(\min(P_i,P_{i+1}) \sim \max(P_i,P_{i+1})\) 之间的铁路经过次数累加 \(1\)，因此考虑采用差分优化，将区间操作转为单点操作即可。
#include<bits/stdc++.h>
#define int long long
using namespace std;
int n,m,ans=0;
int p[100031];
int a[100031],b[100031],c[100031];
int cnt[100031];
signed main(){
cin>>n>>m;
for(int i=1;i<=m;i++) cin>>p[i];
for(int i=1;i<n;i++) cin>>a[i]>>b[i]>>c[i];
for(int i=1;i<m;i++)
cnt[min(p[i],p[i+1])]++,cnt[max(p[i],p[i+1])]--;
for(int i=1;i<=n;i++) cnt[i]+=cnt[i-1];
for(int i=1;i<n;i++) ans+=min(a[i]*cnt[i],b[i]*cnt[i]+c[i]);
cout<<ans;
return 0;
}