POJ 2352 Stars（树状数组）

#include <iostream>
#include <cstring>
#include <cstdio>
#include <algorithm>
#include <cmath>
#include <string>
#include <map>
#include <stack>
#include <queue>
#include <vector>
#define inf 2e9
#define met(a,b) memset(a,b,sizeof a)
typedef long long ll;
using namespace std;
const int N = 2e5+5;
const int M = 4e5+5;
int n,m,tot=0,cnt=0;
int head[N],ans[N];
int tree[33000];
struct man{
    int x,y;
    bool operator< (const man &it)const{
        if(x==it.x)return y<it.y;
        return x<it.x;
    }
}a[N];
void add(int k,int num){
    while(k<=32001){
        tree[k]+=num;
        k+=k&(-k);
    }
}
int Sum(int k){
    int sum=0;
    while(k>0){
        sum+=tree[k];
        k-=k&(-k);
    }
    return sum;
}
int main() {
    met(tree,0);met(head,-1);met(ans,0);
    scanf("%d",&n);
    for(int i=1;i<=n;i++){
        scanf("%d%d",&a[i].x,&a[i].y);
        a[i].x++;a[i].y++;
    }
    sort(a+1,a+1+n);
    for(int i=1;i<=n;i++){
        int sum=Sum(a[i].y);
        ans[sum]++;
        add(a[i].y,1);
    }
    for(int i=0;i<n;i++)printf("%d\n",ans[i]);
    return 0;
}