目录
显示
题目链接
https://www.luogu.org/problem/P2367
题解
区间修改?乍一看似乎要用线段树才能解决。不过读完题目,就会发现只需要在最后求出最小值,并不需要线段树这样的在线算法。
于是自然而然想到差分了,这样只需要 \(O(n)\) 的时间复杂度就可以解决这道题了。
#include <cstdio> #include <algorithm> using namespace std; int a[5000005],diff[5000005],n,p,mina; int main() { scanf("%d%d",&n,&p); for(int i=1;i<=n;i++) { scanf("%d",&a[i]); diff[i]=a[i]-a[i-1]; } for(int i=1;i<=p;i++) { int x,y,z; scanf("%d%d%d",&x,&y,&z); diff[x]+=z; diff[y+1]-=z; } mina=diff[1]; for(int i=1;i<=n;i++) { a[i]=a[i-1]+diff[i]; mina=min(a[i],mina); } printf("%d",mina); return 0; }