【POJ 2352】 Stars

【题目链接】
【算法】
树状数组
注意x坐标为0的情况
【代码】
#include <algorithm>

#include <bitset>

#include <cctype>

#include <cerrno>

#include <clocale>

#include <cmath>

#include <complex>

#include <cstdio>

#include <cstdlib>

#include <cstring>

#include <ctime>

#include <deque>

#include <exception>

#include <fstream>

#include <functional>

#include <limits>

#include <list>

#include <map>

#include <iomanip>

#include <ios>

#include <iosfwd>

#include <iostream>

#include <istream>

#include <ostream>

#include <queue>

#include <set>

#include <sstream>

#include <stdexcept>

#include <streambuf>

#include <string>

#include <utility>

#include <vector>

#include <cwchar>

#include <cwctype>

#include <stack>

#include <limits.h>

using namespace std;

#define MAXN 50010

struct info

{

        int x,y;

} a[MAXN];

int i,n;

int ans[MAXN];

struct BinaryIndexedTree

{

        int c[MAXN];

        inline int lowbit(int x)

        {

                return x & (-x);

        }

        inline void modify(int pos,int val)

        {

                int i;

                for (i = pos; i < MAXN; i += lowbit(i)) c[i] += val;

        }

        inline int query(int pos)

        {

                int i;

                int ret = ;

                for (i = pos; i; i -= lowbit(i))

                        ret += c[i];

                return ret;

        }

} BIT;

int main()

{

        scanf("%d",&n);

        for (i = ; i <= n; i++)

        {

                scanf("%d%d",&a[i].x,&a[i].y);

                a[i].x++; a[i].y++;

        }

        for (i = ; i <= n; i++)

        {

                ans[BIT.query(a[i].x)]++;

                BIT.modify(a[i].x,);

        }

        for (i = ; i < n; i++) printf("%d\n",ans[i]);

        return ;

}