差分(十分简单)

首先初始化数组

const int N=5*1e6+5;
int a[N];
int b[N];

接着输入和初始化差分数组b

 int n,q;
    cin>>n>>q;
    for(int i=1;i<=n;i++){
        cin>>a[i];
        b[i]=a[i]-a[i-1];
    }

进行q次询问

 while(q--){

每次输入xyz,注意头尾

while(q--){
        int x,y,z;
        cin>>x>>y>>z;
        b[x]+=z;
        b[y+1]-=z;
    }

最后赋值

完整代码如下

#include<bits/stdc++.h>
using namespace std;
const int N=5*1e6+5;
int a[N];
int b[N];
int main(){
    int n,q;
    cin>>n>>q;
    for(int i=1;i<=n;i++){
        cin>>a[i];
        b[i]=a[i]-a[i-1];
    }
    while(q--){
        int x,y,z;
        cin>>x>>y>>z;
        b[x]+=z;
        b[y+1]-=z;
    }
    int minn=INT_MAX;
    for(int i=1;i<=n;i++){
        a[i]=b[i]+a[i-1];
        minn=min(minn,a[i]);
    }
    cout<<minn;
    return 0;
}