TouchStone
  请登录后使用
登录 注册
 系统首页  练习题库  考试列表  判题结果  问题讨论与解答  统计信息与排名
  • 首页
  • 题库
  • P1908
  • 题目
  • P1908【线段树】星
    限制 : 时间限制 : 10000 MS   空间限制 : 65536 KB
    问题描述

    宇航员经常检测星图,在星图上,星星由点表示而且每颗星星都有笛卡尔坐标。星星的等级表示左下方(包含正左和正下方)星星的数量。宇航员想知道星星等级的分布。

    例如,如上面图形所示,第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