降临
选定点i会有代价(c_i)，如果一个区间j内的点全被选择，就可以获得回报(p_j)。点数和区间个数(<1e5)。
还以为是线段树优化网络流（50万个点200万条边看上去很可做的样子毕竟lbn说过网络流20万万条边完全没问题），没想到是个线段树dp。
（虽然这两个线段树完全扯不上关系）
用(f[i][j])表示考虑到第i个点，向左最近的尚未选定的点为j时的最大值。那么，i+1可以选也可以不选。不选i时，(f[i][j] ightarrow f[i+1][i+1])。选i时，那么i和左边选过的连续点可以连成区间。则(f[i][j]-c[i+1]+sum_{l[k]>j,r[k]=i+1}p_k ightarrow f[i+1][j])。
我们发现，除了i+1，j只会转移到j。因此，考虑使用线段树维护(f[i])中状态的最大值。转移时，找出所有以i+1为右端点的区间，将他们按照左端点排序，对左端点之间形成的区间统一在线段树上更新即可。
#include <vector>
#include <set>
#include <cstdio>
#include <algorithm>
using namespace std;
typedef long long ll;
typedef pair<ll, ll> pi;
const int maxn=2e6+5;
ll n,m,x,y,z;
ll seg[maxn],add[maxn],c[maxn];
vector<pi> vec[maxn];
void push(ll x){
if (add[x]){
seg[x<<1]+=add[x]; seg[x<<1|1]+=add[x];
add[x<<1]+=add[x]; add[x<<1|1]+=add[x];
add[x]=0; }
}
ll query(ll x,ll l,ll r,ll L,ll R){
if (L<=l&&R>=r) return seg[x];
push(x); ll z=0;
ll mid=(l+r)>>1;
if (L<=mid) z=max(z, query(x<<1, l, mid, L, R));
if (R>mid) z=max(z, query(x<<1|1, mid+1, r, L, R));
return z;
}
void modify(ll x,ll l,ll r,ll L,ll R,ll v){
if (L<=l&&R>=r){ add[x]+=v; seg[x]+=v; return; }
push(x); ll mid=(l+r)>>1;
if (L<=mid) modify(x<<1, l, mid, L, R, v);
if (R>mid) modify(x<<1|1, mid+1, r, L, R, v);
seg[x]=max(seg[x<<1], seg[x<<1|1]);
}
int main(){
scanf("%lld%lld", &n, &m);
for (ll i=1; i<=n; i++) scanf("%lld", &c[i]);
for (ll i=1; i<=m; i++){
scanf("%lld%lld%lld", &x, &y, &z);
vec[y].push_back(make_pair(x,z));
}
for (ll i=1; i<=n; i++){
modify(1,0,n,i,i,query(1,0,n,0,i-1)); //j=i表示不选i
for (ll j=0; j<=(ll)vec[i].size()-1; j++) //加上区间价值
modify(1,0,n,0,vec[i][j].first-1,vec[i][j].second);
modify(1,0,n,0,i-1,-c[i]); //j!=i表示选i，需要减去c[i]
}
printf("%lld
", seg[1]);
return 0;
}