1509：【例 1】Intervals

题目描述

原题来自：Southwestern Europe 2002

给定 $n$ 个闭区间 $[a_i,b_i]$ 和 $n$ 个整数 $c_i$。你需要构造一个整数集合 $Z$，使得对于任意 $i \in [1,n]$，$Z$ 中满足 $a_i \le x \le b_i$ 的整数 $x$ 不少于 $c_i$ 个，求这样的整数集合 $Z$ 最少包含多少个数。

简而言之就是，从 $0 \sim 5 \times 10^4$ 中选出尽量少的整数，使每个区间 $[a_i,b_i]$ 内都有至少 $c_i$ 个数被选出。

输入格式

第一行一个整数 $n$，表示区间个数；

以下 $n$ 行每行描述这些区间，第 $i+1$ 行三个整数 $a_i,b_i,c_i$，由空格隔开。

输出格式

一行，输出满足要求的序列最少整数个数。

样例

样例输入 #1

5
3 7 3
8 10 3
6 8 1
1 3 1
10 11 1

样例输出 #1

6

样例解释 #1

• $n=5$ 个区间：
  1. $[3,7]$ 至少选 $3$ 个数
  2. $[8,10]$ 至少选 $3$ 个数
  3. $[6,8]$ 至少选 $1$ 个数
  4. $[1,3]$ 至少选 $1$ 个数
  5. $[10,11]$ 至少选 $1$ 个数
• 最少选 $6$ 个整数，一种可能的选法是：$\{3,4,5,8,9,10\}$ 或 $\{3,4,6,8,9,10\}$ 等。
  • 区间 $[3,7]$：选了 $3,4,5$（$3$ 个）
  • 区间 $[8,10]$：选了 $8,9,10$（$3$ 个）
  • 区间 $[6,8]$：选了 $8$（$1$ 个）
  • 区间 $[1,3]$：选了 $3$（$1$ 个）
  • 区间 $[10,11]$：选了 $10$（$1$ 个）
• 总数为 $6$。

数据范围

对于全部数据：

• $1 \le n \le 5 \times 10^4$
• $0 \le a_i \le b_i \le 5 \times 10^4$
• $1 \le c_i \le b_i - a_i + 1$

时空限制

• 时间限制：1000 ms
• 内存限制：65536 KB

注意：本题可以转化为差分约束系统。令 $S[x]$ 表示从 $0$ 到 $x$ 中选取的数的个数，则：

1. 每个区间 $[a_i,b_i]$ 要求 $S[b_i] - S[a_i-1] \ge c_i$。
2. 另外，由于 $S$ 是非递减的，有 $S[x] - S[x-1] \ge 0$ 和 $S[x] - S[x-1] \le 1$（因为每个数最多选一次，也可以表示为 $S[x-1] - S[x] \ge -1$）。 然后求 $S[max] - S[-1]$ 的最小值（即最少选多少个数），其中 $S[-1]=0$（可以设为 $S[0-1]=S[-1]=0$，或者整体右移下标）。使用最长路或最短路求解差分约束系统即可。由于 $b_i \le 5\times 10^4$，节点数约 $5\times 10^4+5$，可以用 SPFA 或 Bellman-Ford。