P1908【线段树】星 | |
|
问题描述
宇航员经常检测星图,在星图上,星星由点表示而且每颗星星都有笛卡尔坐标。星星的等级表示左下方(包含正左和正下方)星星的数量。宇航员想知道星星等级的分布。
例如,如上面图形所示,第5号星等级是3 (它由三个标记为1,2和4的星组成)。在此地图上,0等级的星星只有一个(1号),1等级的有两个(2和4号),2等级的有一个(3号),3等级的有一个(5号)。
你设计一个程序,在给定地图上计算出每个等级星星的数量。
输入格式
第一行包含N个星星(1<=N<=200000), 接下来的N行描绘星星的坐标(每行中有两个整数X和Y,由空格分开, 0<=X,Y<=32000)。 在图上的一点只能存在一颗星星,星星根据Y坐标的递增顺序排列,Y坐标相同的星星根据X坐标的递增顺序排列。
输出格式
包含N 行,一行一个数字,第一行包含0等级星星的数量,第二行包含1等级星星的数量,等等,最后一行包含N-1等级星星的数量。
样例输入
5
1 1
5 1
7 1
3 3
5 5
样例输出
1
2
1
1
0