poj2352——Stars//树状数组

44424742

精巧的树状数组：
#include<algorithm>#include<iostream>#include<cstdio>using namespace std;int c[32001];int out[15001];int N=32001;int lowbit(int x){return x&(x^(x-1));}void Modify(int i,int x){while(i<=N){c[i]+=x;i+=lowbit(i);}}int sum(int n){int sum=0;while(n>0){sum+=c[n];n-=lowbit(n);}return sum;}int main(){int n;scanf("%d",&n);int i,x,y;for(i=1;i<=n;i++){scanf("%d%d",&x,&y);x+=1;Modify(x,1);out[sum(x)-1]++;}for(i=0;i<n;i++)printf("%d\n",out[i]);return 0;}