poj 2352 Stars 树状数组

     统计x之前出现数字的次数，线段树和树状数组都可以，但明显树状数组更简洁

/*
author:jxy
lang:C/C++
university:China,Xidian University
**If you need to reprint,please indicate the source**
*/
#include <iostream>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <queue>
#define INF 1E9
using namespace std;
int ans[15005];
int c[32005],n;
inline int low(int x)
{
    return x&-x;
}
int add(int pos,int num)
{
    while(pos<=32001)
    {
        c[pos]+=num;
        pos+=low(pos);
    }
}
int query(int pos)
{
    int ans=0;
    while(pos>0)
    {
        ans+=c[pos];
        pos-=low(pos);
    }
    return ans;
}
int main()
{
    memset(ans,0,sizeof(ans));
    memset(c,0,sizeof(c));
    scanf("%d",&n);
    int i,x,y,t;
    for(i=0;i<n;i++)
    {
        scanf("%d%d",&x,&y);
        x++;
        ans[query(x)]++;
        add(x,1);
    }
    for(i=0;i<n;i++)
      printf("%d\n",ans[i]);
}