mowanggao @ 2024-05-10 17:38:37
//二维前缀和
#include<iostream>
using namespace std;
const int maxn=5e6;
int x,y,z,a[maxn],mmin=maxn,n,t;
int diff[maxn];
int main(){
scanf("%d%d",&n,&t);
for(int i=1;i<=n;i++){
scanf("%d",&a[i]);
}
for(int i=1;i<=n;i++)diff[i]=a[i]-a[i-1];
while(t--){//差分修改 o
scanf("%d%d%d",&x,&y,&z);
diff[x]+=z;
diff[y+1]-=z;
}
for(int i=1;i<=n;i++){//差分修改还原 O
a[i]=a[i-1]+diff[i];
if(a[i]<mmin){
mmin=a[i];
}
}
printf("%d",mmin);
return 0;
}
by SuperAlex4 @ 2024-05-10 17:54:58
a[i]=a[i-1]+diff[i];你再看看这个
by mowanggao @ 2024-05-10 18:39:11
@SuperAlex4 我看不出来，这步不是对差分进行前缀和吗，我看第一个题解也是这样写，求lao提点一下
by SuperAlex4 @ 2024-05-10 18:43:11
@mowanggao 哦我刚看错了（
是你数组开小了，大小应该开得比 5e6 大一点
by mowanggao @ 2024-05-10 18:49:51
@SuperAlex4 谢谢，感谢关注了，为什么有的时候这个数组开正好可以ac，以后是不是都得开的比范围大一点？
by SuperAlex4 @ 2024-05-10 18:59:11
@mowanggao 习惯上都是开大 我平常都开大 100 多（
主要还是开大一点不用考虑 a[1000] 需要用 1001 的空间或者一些字符串多一个 \0 也会占空间 越界会出各种调不出来的问题 那还不如直接开大一点 也不缺这点空间（
by mowanggao @ 2024-05-10 22:17:11
@SuperAlex4 好的谢谢lao