题目链接
解析
对比赛排序然后 DP 并不好做，考虑对道路设计状态。
设 \(f_{i}\) 表示考虑了前 \(i\) 条道路的最大利润。那么有：
\(f_{i} = \max(f_{i - 1},\max_{j = 0}^{i - 1} (f_{j} + g_{j + 1,i} - h_{j + 1,i}))\)
其中 \(g_{i,j}\) 表示修复了从 \(i\) 到 \(j\) 的道路后，可以进行的比赛的收益和。\(h_{i,j}\) 表示修复从 \(i\) 到 \(j\) 的道路的代价和。
考虑如何维护 \(\max_{j = 0}^{i - 1} (f_{j} + g_{j + 1,i} - h_{j + 1,i})\)。记 \(\max\) 里面那部分为 \(x_j\)。每当新加进来一条道路 \(i\) 时，对于以 \(i\) 为右端点的比赛 \(k\)，对于 \(j\in [0,lp_k)\)，其变化为：\(x_j \leftarrow x_j + p_{k} - h_{i,i}\)；对于其余 \(j\)，变化为 \(x_j \leftarrow x_j-h_{i,i}\)。
这样问题就变为区间加，区间求 \(\max\)。线段树维护即可。
时间复杂度 \(O(n\log n)\)。
代码
/*
*/
#include <bits/stdc++.h>
#define eps 0.0000000001
#define ls(x) ((x) << 1)
#define rs(x) (((x) << 1) | 1)
#define mid ((l + r) >> 1)
using namespace std;
typedef long long ll;
typedef unsigned ui;
typedef pair<ll, ll> pii;
const int N = 200000 + 5, M = 20, P = 450, mod = 1e9 + 7, mod2 = 1e9 + 7, b1 = 131;
int h[N];
ll f[N];
ll mx[N << 2],tag[N << 2];
void push_up(int p){mx[p] = max(mx[ls(p)],mx[rs(p)]);
}
void add_tag(int p,ll x){tag[p] += x;mx[p] += x;
}
void push_down(int p){if(!tag[p]) return;add_tag(ls(p),tag[p]),add_tag(rs(p),tag[p]);tag[p] = 0;
}
void add(int p,int l,int r,int L,int R,ll x){if(l > R || r < L) return;if(l >= L && r <= R){add_tag(p,x);return;}push_down(p);add(ls(p),l,mid,L,R,x),add(rs(p),mid + 1,r,L,R,x);push_up(p);
}
ll ask(int p,int l,int r,int L,int R){if(l > R || r < L) return -9e18;if(l >= L && r <= R){return mx[p];}push_down(p);return max(ask(ls(p),l,mid,L,R),ask(rs(p),mid + 1,r,L,R));
}
signed main(){ios::sync_with_stdio(false);cin.tie(0), cout.tie(0);
// freopen("in.txt","r",stdin);
// freopen("out.txt","w",stdout);int n,m;cin>>n>>m;for(int i=1;i<=n;i++){cin>>h[i];}vector<pii> v[N];for(int i=1;i<=m;i++){int l,r,p;cin>>l>>r>>p;v[r].push_back({l,p});}for(int i=1;i<=n;i++){add(1,1,n + 1,1,i,-h[i]);for(int j=0;j<v[i].size();j++){int l = v[i][j].first,p = v[i][j].second;add(1,1,n + 1,1,l,p);}ll x = ask(1,1,n + 1,1,i);f[i] = max(f[i - 1],x);add(1,1,n + 1,i + 1,i + 1,f[i]);}cout<<f[n];return 0;}