1611: 涂气球

内存限制：128 MB 时间限制：1.000 S
评测方式：文本比较 命题人：
提交：31 解决：9

题目描述

小周周要过生日了，老周给他准备了 $n$ 个气球作为生日礼物。将 $n$ 个气球排成一排，从左到右依次编号 $1,\ 2,\ 3,\ \dots,\ n-1,\ n$。之后老周准备进行 $m$ 次涂颜色的操作，每次选择两个数 $a,\ b\ (1 \leq a \leq b \leq n)$，给第 $a$ 个气球到第 $b$ 个气球涂一次颜色。
不过 $m$ 次操作后，老周已经忘记他给每个气球涂了多少次颜色了，你能帮他算出每个气球被涂过几次颜色吗？

数据规模

对于 $30\%$ 的数据：$n,\ m \leq 1,000$；
对于 $60\%$ 的数据：$n,\ m \leq 50,000$；
对于 $100\%$ 的数据：$n,\ m \leq 200,000$。

输入

第一行为两个整数 $n,\ m$。
接下来的 $m$ 行，每行包括 $2$ 个整数 $a,\ b\ (1 \leq a \leq b \leq n)$。

输出

一行，包括 $n$ 个整数，第 $i$ 个数代表第 $i$ 个气球总共被涂色的次数。

样例输入 复制 

3 3
1 1
2 2
3 3

样例输出 复制 

1 1 1

提示

样例2输入 

3 3 

1 1 

1 2 

1 3

样例2输出 

3 2 1

样例3输入 

2 1 

1 2

样例3输出 

1 1

来源/分类

提交提交记录统计讨论版露一手!