测试地址：☞
【题目描述】
原题来自：Ural 1028
天空中有一些星星，这些星星都在不同的位置，每个星星有个坐标。如果一个星星的左下方（包含正左和正下）有 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 ≤ 1.5×10^4，0 ≤ x,y ≤ 3.2×10^4。
【思路】
输入时星星按 y 坐标增序给出，y 坐标相同的按 x 坐标增序给出，故排序问题已不需要考虑，那么只要依次统计星星 i 之前 x 坐标小于等于 i.x 的星星有多少，即星星 i 的级别。y坐标没用，显然是一维树状数组应用。
设数组 b[x] 初始为0，表示在 x 坐标处星星的个数，则求和 b[0] ~ b[x] 则为该星星的等级。
有一个地方尤其要注意，树状数组是以 1 号为起始的，而且只能用 1 号。x 可能为 0，为 0 会时陷入死循环，处理时要将所有的x+1。
还有就是 x 的范围不能事先确定，在 update 的时候直接加到 x 取值范围的最大值，0 ≤ x,y ≤ 3.2×10^4。即 32001，或者在输入的时候找一个 x 的最大值。
【AC代码】
#include<cstdio> const int maxn=1e6+7; int c[maxn], b[maxn]; // c数组为树状数组，b数组用来统计0~n-1级的星星的数目 int n, x, y; int Lowbit(int x){ return x&(-x); } void update(int x, int y){ for(int i = x; i <= 32001; i+=Lowbit(i)) c[i] += y; } int sum(int x){ int sumn=0; for(int i = x; i > 0; i-=Lowbit(i)) sumn += c[i]; return sumn; } int main(){ scanf("%d", &n); for(int i = 1; i <= n; i++){ scanf("%d%d", &x, &y); b[sum(x+1)]++; update(x+1, 1); } for(int i = 0; i < n; i++) printf("%d\n", b[i]); return 0; }
