pku2352专题

PKU2352 Stars - 树状数组

题目描述: 按照y坐标升序,x坐标升序输入N个星星的坐标。若左下角有k个星星,定义星星的级别为k。输出级别为0~N-1的星星分别有多少。 分析: 输入顺序已排好序,那么只要依次统计星星i之前x坐标小于等于i.x的星星有多少,即是星星i的级别。 这样也就成了树状数组的模型。编码很简单,y坐标没用。 注意,x可能为0,处理时要将所有的x+1。(用树状数组的时候一定要注意这一点)还有就是x的范