AT_dp_w Intervals

题目描述

考虑一个长度为 $N$、仅由 0 和 1 组成的字符串。该字符串的分数按照如下方式计算：

• 对于每个 $i$（$1 \leq i \leq M$），如果从第 $l_i$ 个字符到第 $r_i$ 个字符之间至少包含一个 1，则将 $a_i$ 加到分数上。

请你求出字符串分数的最大值。

输入格式

输入以如下格式从标准输入读入。

$N$ $M$ $l_1$ $r_1$ $a_1$ $l_2$ $r_2$ $a_2$ $\ldots$ $l_M$ $r_M$ $a_M$

输出格式

输出字符串分数的最大值。

输入输出样例 #1

输入 #1

5 3
1 3 10
2 4 -10
3 5 10

输出 #1

20

输入输出样例 #2

输入 #2

3 4
1 3 100
1 1 -10
2 2 -20
3 3 -30

输出 #2

90

输入输出样例 #3

输入 #3

1 1
1 1 -10

输出 #3

0

输入输出样例 #4

输入 #4

1 5
1 1 1000000000
1 1 1000000000
1 1 1000000000
1 1 1000000000
1 1 1000000000

输出 #4

5000000000

输入输出样例 #5

输入 #5

6 8
5 5 3
1 1 10
1 6 -8
3 6 5
3 4 9
5 5 -2
1 3 -6
4 6 -7

输出 #5

10

说明/提示

限制条件

• 所有输入均为整数。
• $1 \leq N \leq 2 \times 10^5$
• $1 \leq M \leq 2 \times 10^5$
• $1 \leq l_i \leq r_i \leq N$
• $|a_i| \leq 10^9$

样例解释 1

10001 的分数为 $a_1 + a_3 = 10 + 10 = 20$。

样例解释 2

100 的分数为 $a_1 + a_2 = 100 + (-10) = 90$。

样例解释 3

0 的分数为 $0$。

样例解释 4

答案可能超出 32 位整数范围。

样例解释 5

例如，101000 的分数为 $a_2 + a_3 + a_4 + a_5 + a_7 = 10 + (-8) + 5 + 9 + (-6) = 10$。

由 ChatGPT 4.1 翻译