Toggle navigation
首页
讨论版
入门知识
题库
状态
排名
竞赛&作业
下载
Login
问题 1942. -- 数星星
1942: 数星星
时间限制:
1 Sec
内存限制:
128 MB
提交:
8
解决:
5
[
提交
][
状态
][
讨论版
]
题目描述
天空中有一些星星,这些星星都在不同的位置,每个星星有个坐标。如果一个星星的左下方(包含正左和正下)有k 颗星星,就说这颗星星是 k 级的。
例如,上图中星星 5 是 3 级的(1,2,4在它左下),星星 2,4 是 1 级的。例图中有 1 个 0 级,2 个 1级,1 个 2 级,1个 3 级的星星。
编程任务:
给定星星的位置,输出各级星星的数目。
给定 n 个点,定义每个点的等级是在该点左下方(含正左、正下)的点的数目,试统计每个等级有多少个点。
输入
第一行一个整数 N,表示星星的数目;
接下来 N 行给出每颗星星的坐标,坐标用两个整数 x,y 表示;
不会有星星重叠。星星按 y 坐标增序给出,y坐标相同的按 x 坐标增序给出。
输出
N 行,每行一个整数,分别是 0 级,1 级,2 级,……,N−1 级的星星的数目.
样例输入
5 1 1 5 1 7 1 3 3 5 5
样例输出
1 2 1 1 0
提示
数据范围:对于全部数据,1 <= n <= 15000;0 <= x,y <= 32000
来源
树状/线段树
[
提交
][
状态
]