题意

你是汽车比赛的组织者，现在你将要在线性王国组织几场比赛。

线性王国有n条连续的公路，方向由左到右。我们对公路从左到右分别用1-n进行编号。这样，汽车就是沿着编号变大的方向行驶。有几场比赛可能将要在这里举行。每场比赛将会用到线性王国中的某一段连续的道路。对于每一场比赛，如果它举行了，你将会得到一定的费用作为报酬。这些比赛都是分开举行的，所以道路可以重复使用。

但是很不幸的，所有的道路都是坏的。所以还不能举行任何比赛。每条道路有对应的修理费用。如果一场比赛想要举行，那么它所要用到的所有道路都必须修好。你的任务是，修理某几条道路（可能是所有，也可能一条也不用），然后举行其中某些赛事，以获取最大的利润。利润的计算方法是举行赛事得到的报酬减去修理道路的费用。当然你也可以一条道路也不修，然后利润是0。

样例解释：

在样例中，最佳方案是把1，2，3和7号道路修好。然后举行三个赛事，你将可以得到15，修理费用为11，总利润为4。

题解

这题维护一个类似于前缀和的东西就可以了
按rr<script type="math/tex" id="MathJax-Element-40">r</script>扫过去
每加入一条线段，就会使得一段前缀和变大
大概就是维护一下左端点放在哪里会损失多少代价
f[i]转移就可以了
每一次选择一个最小的

CODE:

#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<algorithm>
#include<iostream>
using namespace std;
typedef long long LL;
const int N=200005;
int n,m;
LL s[N];
struct qq{int l,r,x;}q[N];
bool cmp (qq x,qq y){
   return x.r<y.r;}
struct qt
{int l,r;int s1,s2;LL c;LL lazy;
}tr[N*2];int num=0;
void bt (int l,int r)
{int a=++num;tr[a].l=l;tr[a].r=r;tr[a].c=-s[l];tr[a].lazy=0;if (l==r) return ;int mid=(l+r)>>1;tr[a].s1=num+1;bt(l,mid);tr[a].s2=num+1;bt(mid+1,r);tr[a].c=min(tr[tr[a].s1].c,tr[tr[a].s2].c);
}
void push_down (int now)
{int s1=tr[now].s1,s2=tr[now].s2;tr[s1].c+=tr[now].lazy;tr[s1].lazy+=tr[now].lazy;tr[s2].c+=tr[now].lazy;tr[s2].lazy+=tr[now].lazy;tr[now].lazy=0;
}
void change (int now,int l,int r,LL x)
{if (l>r) return ;if (tr[now].l==l&&tr[now].r==r){tr[now].c+=x;tr[now].lazy+=x;return ;}push_down(now);int s1=tr[now].s1,s2=tr[now].s2;int mid=(tr[now].l+tr[now].r)>>1;if (r<=mid) change(s1,l,r,x);else if (l>mid) change(s2,l,r,x);else change(s1,l,mid,x),change(s2,mid+1,r,x);tr[now].c=min(tr[s1].c,tr[s2].c);
}
LL find (int now,int l,int r)
{if (l>r) return 0;if (tr[now].l==l&&tr[now].r==r) return tr[now].c;push_down(now);int s1=tr[now].s1,s2=tr[now].s2;int mid=(tr[now].l+tr[now].r)>>1;if (r<=mid) return find(s1,l,r);else if (l>mid) return find(s2,l,r);else return min(find(s1,l,mid),find(s2,mid+1,r));
}
LL f[N];
int main()
{scanf("%d%d",&n,&m);for (int u=1;u<=n;u++){scanf("%lld",&s[u]);s[u]=s[u-1]+s[u];}bt(0,n);for (int u=1;u<=m;u++)  scanf("%d%d%d",&q[u].l,&q[u].r,&q[u].x);sort(q+1,q+1+m,cmp);int now=0;LL sum=0;for (int u=1;u<=n;u++)//修到第几条路 {f[u]=f[u-1];while (now<m&&q[now+1].r<=u){now++;sum=sum+q[now].x;change(1,q[now].l,n,q[now].x);}f[u]=max(f[u],sum-s[u]-find(1,0,u-1));change(1,u,u,-f[u]);}printf("%lld\n",f[n]);return 0;
}