[洛谷 2367]语文成绩

题目链接

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;
}