题目大意
给定 \(m\) 条形如 \((l_i,r_i,a_i)\) 的规则，你需要求出一个长为 \(n\) 的分数最大的 01 串的分数，其中一个 01 串 \(A\) 的分数被定义为
\[\sum_{i=1}^ma_i[\sum_{j=l_i}^{r_i}A_j\ge 1]
\]
思路分析
考虑 DP。
设 \(f_{i,j}\) 表示考虑 01 串的前 \(i\) 个数，最后一个 \(1\) 放在 \(j\) 时的最大分数，首先有一个特殊的转移：
\[f_{i,i}=\max_{j<i}(f_{i-1,j})
\]
也就是枚举前 \(i-1\) 个数中上一个 \(1\) 放在哪个位置，对所有可能的情况取 \(\max\)。
考虑一般情况：
从 \(i-1\) 转移到 \(i\)，新的贡献只从所有右端点为 \(i\) 的区间产生，考虑到产生贡献的条件是至少包含一个 \(1\)，而最后的 \(1\) 位于 \(j\)，故只有这个区间包含 \(j\) 的时候才会产生贡献，故有状态转移方程：
\[f_{i,j}=f_{i-1,j}+\sum_{k=1}^m[l_k\le j][r_k=i]a_k
\]
直接转移的时间复杂度是 \(O(n^3)\) 的，不过可以通过将区间排序加双指针做到均摊 \(O(n^2)\)，但依然无法通过，考虑优化。
首先发现转移只与上一维有关，可以直接优化掉 \(i\)，使空间复杂度降为 \(O(n)\)。
考虑哪些区间对 \(f\) 产生贡献，不难发现，只要区间包含 \(f\) 的端点，它就对 \(f\) 有贡献，那么我们就可以把 \(f\) 丢到线段树上，对于每一个区间进行一次线段树上的区间加操作，维护区间的最大值即可。
注意 01 串全为 \(0\) 时其分数为 \(0\)，故不可能产生负分数，所有的分数需要和 \(0\) 取 \(\max\)。
代码
#include <algorithm>
#include <iostream>
#include <cstring>
#include <vector>
#include <cstdio>
#include <cmath>
using namespace std;
const int N=200200;
#define int long long
#define mid ((l+r)>>1)
int n,m,in1,in2,in3;
struct Node{
int l,r,a;
}a[N];
vector<Node> v[N];
struct ST{
int maxn[N<<2],tag[N<<2];
void change_t(int p,int k){
maxn[p]+=k;tag[p]+=k;
}
void push_down(int p){
if(!tag[p]) return ;
change_t(p<<1,tag[p]);
change_t(p<<1|1,tag[p]);
tag[p]=0;
}
void change(int p,int l,int r,int x,int y,int k){
if(x<=l&&r<=y){change_t(p,k);return ;}
push_down(p);
if(x<=mid) change(p<<1,l,mid,x,y,k);
if(y>mid) change(p<<1|1,mid+1,r,x,y,k);
maxn[p]=max(maxn[p<<1],maxn[p<<1|1]);
}
}tree;
signed main(){
scanf("%lld%lld",&n,&m);
for(int i=1;i<=m;i++){
scanf("%lld%lld%lld",&in1,&in2,&in3);
a[i]=Node{in1,in2,in3};
v[in2].push_back(a[i]);
}
for(int i=1;i<=n;i++){
tree.change(1,1,n,i,i,max(tree.maxn[1],0ll));
for(auto it:v[i])
tree.change(1,1,n,it.l,i,it.a);
}
cout<<max(tree.maxn[1],0ll)<<'\n';
return 0;
}