A3001. 种树
编程题
普及-
知识点
题目描述
一条街的一边有几座房子，因为环保原因居民想要在路边种些树。路边的地区被分割成块，并被编号成 $1, 2, \ldots,n$。每个部分为一个单位尺寸大小并最多可种一棵树。
每个居民都想在门前种些树，并指定了三个号码 $b$，$e$，$t$。这三个数表示该居民想在地区 $b$ 和 $e$ 之间（包括 $b$ 和 $e$）种至少 $t$ 棵树。
居民们想种树的各自区域可以交叉。你的任务是求出能满足所有要求的最少的树的数量。
每个居民都想在门前种些树，并指定了三个号码 $b$，$e$，$t$。这三个数表示该居民想在地区 $b$ 和 $e$ 之间（包括 $b$ 和 $e$）种至少 $t$ 棵树。
居民们想种树的各自区域可以交叉。你的任务是求出能满足所有要求的最少的树的数量。
输入格式
输入的第一行是一个整数，代表区域的个数 $n$。
输入的第二行是一个整数，代表房子个数 $h$。
第 $3$ 到第 $(h + 2)$ 行，每行三个整数，第 $(i + 2)$ 行的整数依次为 $b_i, e_i, t_i$，代表第 $i$ 个居民想在 $b_i$ 和 $e_i$ 之间种至少 $t_i$ 棵树。
输入的第二行是一个整数，代表房子个数 $h$。
第 $3$ 到第 $(h + 2)$ 行，每行三个整数，第 $(i + 2)$ 行的整数依次为 $b_i, e_i, t_i$，代表第 $i$ 个居民想在 $b_i$ 和 $e_i$ 之间种至少 $t_i$ 棵树。
输出格式
输出一行一个整数，代表最少的树木个数。
输入输出样例
输入 #1
9 4 1 4 2 4 6 2 8 9 2 3 5 2
输出 #1
5
说明/提示
#### 数据规模与约定
对于 $100\%$ 的数据，保证：
- $1 \leq n \leq 3 \times 10^4$，$1 \leq h \leq 5 \times 10^3$。
- $1 \leq b_i \leq e_i \leq n$，$1 \leq t_i \leq e_i - b_i + 1$。
对于 $100\%$ 的数据，保证：
- $1 \leq n \leq 3 \times 10^4$，$1 \leq h \leq 5 \times 10^3$。
- $1 \leq b_i \leq e_i \leq n$，$1 \leq t_i \leq e_i - b_i + 1$。