标准的差分应用题,不要想的太复杂,写成了线段树。
1 #include<bits/stdc++.h>
2 using namespace std;
3 const int N=5e6+10;
4 int d[N],a[N];//d是差分数组
5 int n,p,x,y,z,ans=1e9;
6 int main(){
7 scanf("%d%d",&n,&p);
8 for(int i=1;i<=n;i++) scanf("%d",&a[i]);
9 for(int i=1;i<=n;i++) d[i]=a[i]-a[i-1];
10 for(int i=1;i<=p;i++){
11 scanf("%d%d%d",&x,&y,&z);
12 d[x]+=z;d[y+1]-=z;
13 }
14 for(int i=1;i<=n;i++){
15 a[i]=a[i-1]+d[i];
16 ans=min(ans,a[i]);
17 }
18 cout<<ans;
19 }