A7064. 01串分数最值
编程题
提高+/省选-
知识点
题目描述
给定一个长度为 $N$、只由
对每个区间 $[l_i,r_i]$：
- 如果在第 $l_i$ 个字符到第 $r_i$ 个字符之间**至少出现一个**
- 否则这个区间对分数贡献为 $0$。
请你求这个字符串分数的最大值。
0 和 1 组成的字符串。它的分数按如下规则计算：对每个区间 $[l_i,r_i]$：
- 如果在第 $l_i$ 个字符到第 $r_i$ 个字符之间**至少出现一个**
1，则把 $a_i$ 加到分数中；- 否则这个区间对分数贡献为 $0$。
请你求这个字符串分数的最大值。
输入格式
第一行包含两个整数 $N,M$。
接下来 $M$ 行，每行包含三个整数 $l_i,r_i,a_i$。
接下来 $M$ 行，每行包含三个整数 $l_i,r_i,a_i$。
输出格式
输出一个整数，表示最大可能分数。
输入输出样例
输入 #1
5 3 1 3 10 2 4 -10 3 5 10
输出 #1
20
输入 #2
3 4 1 3 100 1 1 -10 2 2 -20 3 3 -30
输出 #2
90
输入 #3
1 1 1 1 -10
输出 #3
0
输入 #4
1 5 1 1 1000000000 1 1 1000000000 1 1 1000000000 1 1 1000000000 1 1 1000000000
输出 #4
5000000000
输入 #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 \le N \le 2 \times 10^5$
- $1 \le M \le 2 \times 10^5$
- $1 \le l_i \le r_i \le N$
- $|a_i| \le 10^9$
## 样例解释
- 样例解释 1：取字符串
- 样例解释 2：取字符串
- 样例解释 3：取字符串
- 样例解释 4：取字符串
- 样例解释 5：例如取字符串
- $1 \le N \le 2 \times 10^5$
- $1 \le M \le 2 \times 10^5$
- $1 \le l_i \le r_i \le N$
- $|a_i| \le 10^9$
## 样例解释
- 样例解释 1：取字符串
10001，区间 $[1,3]$ 和 $[3,5]$ 内都有 1，得到 $a_1+a_3=10+10=20$。- 样例解释 2：取字符串
100，区间 $[1,3]$ 和 $[1,1]$ 内有 1，得到 $a_1+a_2=100+(-10)=90$。- 样例解释 3：取字符串
0，得分为 $0$。- 样例解释 4：取字符串
1，五个区间都被满足，总分为 $5 \times 10^9$。- 样例解释 5：例如取字符串
101000，得到 $a_2+a_3+a_4+a_5+a_7=10+(-8)+5+9+(-6)=10$。