$j \le$ 当前区间的左端点
这个条件满足的时候会有影响，所以我们把 $1$ 到当前这个区间的左端点给区间加上当前区间的价值（ ~~可能会有点绕，~~ 仔细想想就明白了）。
$s(j,i)$ 的处理就用一个前缀和就好了。
由此，我们可以得出这么一个方程式：
$$
f_i = \max ( f_{i-1} , \max ( f_{j-1} + sum(j,i) + s(j,i) (1 \le j \le i ) ) )
$$
上面那个式子第二个 $max$ 之前的东西都很好理解，说一下第二个 $max$ 里面的东西。
$f_{j-1}$ 表示第 $j$ 个之前最大的利益，所以这后半部分的式子表示有一个从 $j$ 到 $i$ 的区间我们全部选择。
这样子我们就得到了一个时间复杂度是 $O(n^2)$ 级别的解法，但是数据范围是 $10^6$，所以肯定会炸，考虑优化。
我们发现这整个式子其实是由两个 $max$ 组成的，而且我们发现第一个 $max$ 可以 $O(1)$ 做，第二个 $max$ 可以用线段树来优化，而且我们加入新的区间时也可以用线段树来区间加，所以总复杂度为 $O(n \log n)$。
具体实现的话，看代码吧。~~码风稍微有点奇怪，希望不影响阅读。~~
## **Code：**
```cpp
#include <iostream>
#include <vector>
#include <cstdio>
using namespace std ;
const long long INF = 0x3f3f3f3f3f3f3f3f ;
struct Node
{
int l , r ;
long long v ;
} q[1000005] ;
int n , m ;
long long s[1000005] , f[1000005] , t[4000005] , lz[4000005] ;
vector < int > vc[1000005] ;
void build ( int k , int l , int r )
{
if ( l == r )
{
t [ k ] = s [ l - 1 ] ;
return ;
}
int mid = ( l + r ) >> 1 ;
build ( k << 1 , l , mid ) ;
build ( k << 1 | 1 , mid + 1 , r ) ;
t [ k ] = max ( t [ k << 1 ] , t [ k << 1 | 1 ] ) ;
}
void pushdown ( int k )
{
if ( lz [ k ] )
{
t [ k << 1 ] += lz [ k ] ;
t [ k << 1 | 1 ] += lz [ k ] ;
lz [ k << 1 ] += lz [ k ] ;
lz [ k << 1 | 1 ] += lz [ k ] ;
lz [ k ] = 0 ;
}
}
void change ( int k , int l , int r , int x , int y , long long z )
{
if ( x <= l && r <= y )
{
t [ k ] += z ;
lz [ k ] += z ;
return ;
}
pushdown ( k ) ;
int mid = ( l + r ) >> 1 ;
if ( x <= mid )
change ( k << 1 , l , mid , x , y , z ) ;
if ( y > mid )
change ( k << 1 | 1 , mid + 1 , r , x , y , z ) ;
t [ k ] = max ( t [ k << 1 ] , t [ k << 1 | 1 ] ) ;
}
long long query ( int k , int l , int r , int x , int y )
{
if ( x <= l && r <= y )
return t [ k ] ;
pushdown ( k ) ;
int mid = ( l + r ) >> 1 ;
long long res = -INF ;
if ( x <= mid )
res = query ( k << 1 , l , mid , x , y ) ;
if ( y > mid )
res = max ( res , query ( k << 1 | 1 , mid + 1 , r , x , y ) ) ;
return res ;
}
int main ( )
{
cin >> n >> m ;
for ( int i = 1 ; i <= n ; ++ i )
{
long long x ;
cin >> x ;
s [ i ] = s [ i - 1 ] + x ;
}
for ( int i = 1 ; i <= m ; ++ i )
{
cin >> q [ i ] .l >> q [ i ] .r >> q [ i ] .v ;
vc [ q [ i ] .r ] .push_back ( i ) ;
}
f [ 0 ] = 0 ;
build ( 1 , 1 , n ) ;
for ( int i = 1 ; i <= n ; ++ i )
{
for ( int j = 0 ; j < ( int ) vc [ i ] .size ( ) ; ++ j )
change ( 1 , 1 , n , 1 , q [ vc [ i ] [ j ] ] .l , q [ vc [ i ] [ j ] ] .v ) ;
f [ i ] = max ( f [ i - 1 ] , query ( 1 , 1 , n , 1 , i ) - s [ i ] ) ;
change ( 1 , 1 , n , i + 1 , i + 1 , f [ i ] ) ;
}
cout << f [ n ] << endl ;
return 0 ;
}
```