2546. Color the ball
1000ms
512MB
简单
树状数组
题目描述
有 $N$ 个气球排成一排，从左到右依次编号为 $1, 2, 3, \dots, N$。初始时，所有气球都没有被涂色（我们可以认为每个气球的涂色次数为 0）。
现在需要进行 $N$ 次涂色操作。每次操作给定一个区间 $[a, b]$（$1 \le a \le b \le N$），表示将编号从 $a$ 到 $b$ 的所有气球都**涂一次颜色**。
经过所有操作后，请计算出每个气球最终被涂了多少次颜色。
输入格式
输入包含多组测试数据。
- 每组测试数据的第一行包含一个整数 $N$ ($1 \le N \le 100,000$)，表示气球的数量，同时也表示需要进行 $N$ 次涂色操作。
- 接下来 $N$ 行，每行包含两个整数 $a$ 和 $b$ ($1 \le a \le b \le N$)，表示一次涂色操作的区间。
- 当 $N = 0$ 时，输入结束，程序退出。
输出格式
对于每组测试数据，输出一行，包含 $N$ 个整数，用空格隔开。第 $i$ 个整数表示第 $i$ 个气球被涂色的总次数。
样例 1
输入 (Input)
输出 (Output)
样例说明
*(样例解释：第一组数据中，3个气球分别被涂了1次；第二组数据中，气球1被涂了3次，气球2被涂了2次，气球3被涂了1次。)*
› 输入 stdin
CtrlShiftEnter
‹ 输出 stdout
错误 stderr
操作成功