POJ2352 Stars

题目大意

按纵坐标升序给定N颗星星的坐标(x[i],y[i])，计算出每个等级的星星有多少，对于等级是这样定义的：对于第i颗星星，计算出1~i-1颗星星中横坐标和纵坐标都比第i颗星星小的数量ans，那么ans就是此颗星星的等级。

题解

很经典的树状数组入门题目，直接看代码吧，不过有一个地方要注意，就是横坐标为0的情况，如果在更新的时候循环用的是while(x<=MAXS)，对于x=0的情况，会无限循环，因为x+lowbit(x)依然是0，因此我们对于所有的横坐标都加1,这样就解决这个问题

代码

#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cstring>
#define MAXN 15005
#define MAXS 32005
using namespace std;
int f[MAXN];
int c[MAXS];
int n;
int lowbit(int x)
{
    return x&-x;
}
void add(int x,int d)
{
 while(x<=MAXS)
 {
     c[x]+=d;
     x+=lowbit(x);
}
}
int sum(int x)
{
    int ret=0;
    while(x>0)
    {
        ret+=c[x];
        x-=lowbit(x);
    }
    return ret;
}
int main(void)
{
    int i,x,y;
    cin>>n;
    memset(c,0,sizeof(c));
    memset(f,0,sizeof(f));
    for(i=1;i<=n;i++)
    {
        scanf("%d%d",&x,&y);
        x++;
        f[sum(x)]++;
         add(x,1);
    }
    for(i=0;i<n;i++)
    printf("%d\n",f[i]);
    return 0;
}