Stars

gistfile1.cpp

#include <cstdio>
#include <cstring>
#include <algorithm>
#include <cmath>
#define z0(x) memset(x, 0, sizeof(x))
#define z1(x) memset(x, -1, sizeof(x))
#define N 150010

using namespace std;
typedef struct star{
    int x, y;
}star;
int c[N];
int ans[N];
star stars[N];
int n;
int lowbit(int x)
{
    return x&(-x);
}
int sum(int n)
{
    int sum = 0;
    while (n > 0){
        sum += c[n];
        n -= lowbit(n); //?
    }
    return sum;
}
void updata(int i, int num)
{
    while (i <= n){
        c[i] += num;
        i += lowbit(i);
    }
}
int main()
{
    z0(stars); z0(c); z0(ans);
    scanf("%d",&n);
    for (int i = 0; i < n; i++){
        scanf("%d%d",&stars[i].x, &stars[i].y);
        stars[i].x++;
    }
    for (int i = 0; i < n; i++){
        ans[sum(stars[i].x)]++;
        updata(stars[i].x,1);
    }
    for (int i = 0; i < n; i++){ 
        printf("%d\n",ans[i]);
    }
    system("pause.");
    return 0;
}