有 \(m\) 条形如 \((l, r, a)\) 的限制，表示如果 \(s_{[l, r]}\) 中有 1 就会有 \(a\) 的价值。
你要求长度为 \(n\) 的 01 串的价值的最大值。
\(n, m \le 2 \times 10^5\)。
将每个限制挂到右端点上，在右端点处计算贡献。然后我们就只关心最后一个 1 出现的位置了。
所以设计 dp 状态为 \(f_{i, j}\) 表示考虑了前 \(i\) 位，最后一个 1 的位置为 \(j\) 的方案数。
转移就分类讨论一下这一位填 1 还是填 0：
\[ \begin{aligned} &f_{i, j} \leftarrow f_{i - 1, j} + \sum_{l_k \le j, r_k = i} a_k \\ &f_{i, i} \leftarrow \max_{j \in [0, i - 1]} f_{i - 1, j} + \sum_{l_k \le j, r_k = i} a_k \end{aligned} \]第一个转移是第 \(i\) 位填 1 的，第二个是第 \(i\) 位填 0 的。
但这个是 \(O(n^2)\) 的，还要继续优化。
首先把第一维滚掉，变成：
\[ \begin{aligned} &f_{j} \leftarrow f_{j} + \sum_{l_k \le j, r_k = i} a_k \\ &f_{i} \leftarrow \max_{j \in [0, i - 1]} f_{j} + \sum_{l_k \le j, r_k = i} a_k \end{aligned} \]然后就可以发现这个可以扔到线段树上变成区间加，区间 \(\max\)。
时间复杂度 \(O(n \log n)\)。
constexpr int MAXN = 2e5 + 9;
int n, m;
vector<pair<int, int> > vec[MAXN];
struct Node {
ll sum, mx, add;
Node(): sum(0), mx(0), add(0) { return; }
Node(ll _s, ll _m, ll _a): sum(_s), mx(_m), add(_a) { return; }
} sgt[MAXN << 2];
void Push_Tag(int p, int len, ll k) {
sgt[p].sum += k * len;
sgt[p].mx += k;
sgt[p].add += k;
return;
}
void Push_Up(int p) {
sgt[p].sum = sgt[p << 1].sum + sgt[p << 1 | 1].sum;
sgt[p].mx = max(sgt[p << 1].mx, sgt[p << 1 | 1].mx);
return;
}
void Push_Down(int p, int L, int R) {
if (sgt[p].add) {
int Mid = L + R >> 1;
Push_Tag(p << 1, Mid - L + 1, sgt[p].add);
Push_Tag(p << 1 | 1, R - Mid, sgt[p].add);
sgt[p].add = 0;
}
return;
}
void Update(int l, int r, ll k, int L = 0, int R = n, int p = 1) {
if (l <= L && R <= r) return Push_Tag(p, R - L + 1, k);
Push_Down(p, L, R); int Mid = L + R >> 1;
if (l <= Mid) Update(l, r, k, L, Mid, p << 1);
if (Mid < r) Update(l, r, k, Mid + 1, R, p << 1 | 1);
Push_Up(p); return;
}
void slv() {
n = Read<int>(), m = Read<int>();
for (int i = 1; i <= m; i ++) {
int l = Read<int>(), r = Read<int>(), a = Read<int>();
vec[r].emplace_back(l, a);
}
for (int r = 1; r <= n; r ++) {
Update(r, r, sgt[1].mx);
for (auto [l, a] : vec[r]) Update(l, r, a);
}
Write(sgt[1].mx, '\n');
return;
}