Codeforces

Luogu

分析

考虑 DP。设 $dp_i$ 表示前 $i$ 条道路的最大收益，不难得到转移
$$
dp_i=\min_{j<i}\left\{dp_j-c(j+1,i)+w(j+1,i)\right\}
$$
这里的 $c(i,j)$ 表示修建 $i$ 到 $j$ 的道路的花费，$w(i,j)$ 表示修建 $i$ 到 $j$ 的道路获得的收益。

考虑用线段树优化，即要求扫到 $i$ 时每个叶结点的值 $j$ 为 $dp_j-c(j+1,i)+w(j+1,i)$。对于一个新的 $i$，将 $[0,i-1]$ 减去 $c_i$，然后对于所有右端点在 $i$ 的比赛 $k$ ，将 $[0,l_k-1]$ 加上 $w_k$ 即可。事先将比赛按右端点排序并用一个指针维护即可。

代码

// ===================================
//   author: M_sea
//   website: http://m-sea-blog.com/
// ===================================
#include <bits/stdc++.h>
#define re register
using namespace std;
typedef long long ll;

inline int read() {
    int X=0,w=1; char c=getchar();
    while (c<'0'||c>'9') { if (c=='-') w=-1; c=getchar(); }
    while (c>='0'&&c<='9') X=X*10+c-'0',c=getchar();
    return X*w;
}

const int N=200000+10;

int n,m,c[N];
struct node { int l,r,w; } a[N];
bool operator <(node a,node b) { return a.r<b.r; }
ll dp[N];

#define ls (o<<1)
#define rs (o<<1|1)
ll maxv[N<<2],addv[N<<2];
inline void update(int o,ll w) { addv[o]+=w,maxv[o]+=w; }
inline void pushup(int o) { maxv[o]=max(maxv[ls],maxv[rs]); }
inline void pushdown(int o) {
    if (addv[o]) update(ls,addv[o]),update(rs,addv[o]),addv[o]=0;
}
inline void modify(int o,int l,int r,int ql,int qr,ll w) {
    if (ql<=l&&r<=qr) { update(o,w); return; }
    int mid=(l+r)>>1; pushdown(o);
    if (ql<=mid) modify(ls,l,mid,ql,qr,w);
    if (qr>mid) modify(rs,mid+1,r,ql,qr,w);
    pushup(o);
}
inline ll query(int o,int l,int r,int ql,int qr) {
    if (ql<=l&&r<=qr) return maxv[o];
    int mid=(l+r)>>1; ll res=-2e18; pushdown(o);
    if (ql<=mid) res=max(res,query(ls,l,mid,ql,qr));
    if (qr>mid) res=max(res,query(rs,mid+1,r,ql,qr));
    pushup(o); return res;
}
#undef ls
#undef rs

int main() {
    n=read(),m=read();
    for (re int i=1;i<=n;++i) c[i]=read();
    for (re int i=1;i<=m;++i) a[i].l=read(),a[i].r=read(),a[i].w=read();
    sort(a+1,a+m+1);
    for (re int i=1,p=1;i<=n;++i) {
        while (p<=m&&a[p].r<=i) modify(1,0,n,0,a[p].l-1,a[p].w),++p;
        modify(1,0,n,0,i-1,-c[i]);
        dp[i]=max(dp[i-1],query(1,0,n,0,i-1));
        modify(1,0,n,i,i,dp[i]);
    }
    printf("%I64d\n",dp[n]);
    return 0;
}