re80分求调

G1yu @ 2023-10-13 22:44:43

#include<bits/stdc++.h>
using namespace std;
long long n,p,a[1000900],x,y,z,d[1000900],g[1000900];
int main(){
    cin>>n>>p;
    for(int i=1;i<=n;i++){
        cin>>a[i];
        d[i] = a[i]-a[i-1];
    }
    while(p--){
        cin>>x>>y>>z;
        d[x]+=z;
        d[y+1]-=z;
    }
    long long Min = LONG_LONG_MAX;
    for(int i=1;i<=n;i++){
        g[i] = d[i] + g[i-1];
        Min = min(Min,g[i]);
    }
    cout<<Min;

    return 0;
}

by NO_OI_NO_LIFE @ 2023-10-13 22:50:18

线段树好题,数组开成5000005

by muhaoran123456 @ 2023-10-15 10:05:42

N=5e5+5 哦，你写的1e5+900还是小了

by small_beswk @ 2023-10-15 12:46:40

#include<bits/stdc++.h>
using namespace std;
int n,p,a[5000005],x,y,z,d[5000005];
int main(){
    cin>>n>>p;
    for(int i=1;i<=n;i++){
        cin>>a[i];
        d[i] = a[i]-a[i-1];
    }
    while(p--){
        cin>>x>>y>>z;
        d[x]+=z;
        d[y+1]-=z;
    }
    int Min=INT_MAX;
    for(int i=1;i<=n;i++){
        a[i] = d[i] + a[i-1];
        Min = min(Min,a[i]);
    }
    cout<<Min;
    return 0;
}

因为a[]已经没啥大用了，所以把差分数组d[]转前缀和用a[]存着就好了，不用再开一个数组；

其实好像不需要用long long啊......

by G1yu @ 2023-10-22 08:13:39

谢谢各位大佬，已AC