下载掌阅APP，畅读海量书库
立即打开
题目描述（POJ2352）： 星星由平面上的点表示，星星的等级为纵横坐标均不超过自己的星星数量（不包括自己）。下图中，5号星的等级为3（纵横坐标均不超过5号星的星星有3颗：1、2和4号）。2和4号星的级别是1。在该地图上有一颗0级星、两颗1级星、一颗2级星和一颗3级星。计算给定地图上每个级别的星星数量。
输入： 第1行包含星星的数量 N （1≤ N ≤15000）。以下 N 行描述星星的坐标，每行都包含两个整数 X 、 Y （0≤ X ， Y ≤32000）。平面上的一个点只可以有一颗星星。以 Y 坐标升序输入，在 Y 坐标相等时以 X 坐标升序输入。
输出： 输出包含 N 行，第1行包含0级的星星数量，第2行包含1级的星星数量……最后一行包含 N- 1级的星星数量。
提示： 数据量巨大，这里使用scanf而不是cin来读取数据，避免超出时间限制。
题解： 每颗星星的等级都为它左下方的星星个数。输入所有星星（按照 y 升序，若 y 相等，则 x 升序）的坐标，依次输出等级0～ n -1的星星数量。
输入样例的地图如下图所示，图中星星旁边的数字为输入顺序，1号星的左下没有星星，等级为0；2号星的左边有1颗星星，等级为1；3号星的左边有2颗星星，等级为2；4号星的左下有1颗星星，等级为1；5号星的左边有3颗星星，等级为3。因此等级为0的有1个，等级为1的有2个，等级为2的有1个，等级为3的有1个，等级为4的有0个。
本题看似二维数据，实际上输入数据已经按照 y 升序，也就是说，读到一个点时，当前点的 y 坐标肯定大于或等于已经输入的 y 坐标。如果 y 坐标相等，则 x 坐标肯定大于已经输入的 x 坐标，所以每次只要计算 x 坐标比当前点小的点就行了。该问题的本质是统计 x 坐标前面星星的数量，是前缀和问题。因为数据量较大，暴力穷举会超时，所以可以借助树状数组解决。
注意：给的点坐标从0开始，树状数组下标从1开始（0的位置不可用），所以需要在输入 x 坐标时加1处理。
（1）依次输入每一个坐标 x 、 y ，执行 x ++。
（2）计算 x 的前缀和sum( x )，将其作为该星星的等级，用ans[]数组累计该等级的数量。
（3）将树状数组中 x 的数量加1。
