http://blog.csdn.net/niushuai666/article/details/7389273
题目链接：http://poj.org/problem?id=2352
题目大意：
给你星星的坐标（y递增，若y相等，x递增），每个星星都有一个等级，规定它的等级就是在它左下方的星星的个数。输入所有星星后，依次输出等级为0到n-1的星星的个数。
解题思路：
就是统计x前面比它小的星星的个数，符合树状数组最基本的应用。
注意的是：树状数组下标为0的位置不可用，所以我们需要在输入x坐标时+1.
由于y坐标是升序的且坐标不重复，所以在星星A后面输入的星星的x,y坐标不可能都小于等于星星A。假如当前输入的星星为（3,3），易得我们只需要去找 树状数组中小于等于3的值就可以了，即GetSum(3)。注意：A[i]表示x坐标为i的个数，C[]为A[]的树状数组，那么GetSum(i)就是 序列中前i个元素的和，即x小于等于i的星星数。
代码如下：
- #include<iostream>
- #include<string>
- #include<cstring>
- #include<cstdio>
- #include<algorithm>
- using namespace std;
- #define CLR(arr, val) memset(arr, val, sizeof(arr))
- #define N 32010
- int n;
- int lev[N], c[N];
- int lowbit(int x)
- {
- return x & (-x);
- }
- void add(int i, int data)
- {
- while(i < N)
- {
- c[i] += data;
- i += lowbit(i);
- }
- }
- int getsum(int x)
- {
- int res = 0;
- while(x > 0)
- {
- res += c[x];
- x -= lowbit(x);
- }
- return res;
- }
- int main()
- {
- int x, y;
- while(~scanf("%d", &n))
- {
- CLR(lev, 0); CLR(c, 0);
- for(int i = 0; i < n; ++i)
- {
- scanf("%d%d", &x, &y);
- x++; //有0出现，树状数组无法处理。故+1
- lev[getsum(x)]++; //先统计，不包括本身
- add(x, 1); //加入
- }
- for(int i = 0; i < n; ++i)
- printf("%d\n", lev[i]);
- }
- return 0;
- }