题意:给出n个星星以坐标形式(X,Y),顺序为先按y排序,再按x排序。求出每个等级的星星个数。星星的等级是按照其左下方的星星个数表示的,包括正左和正下的
因为星星坐标是按照y的升序给出的所以我们只要考虑x便可以,把x放进数状数组里。
#include<stdio.h> const int maxn=32005; int C[maxn]; int lowbit(int x){ return x&(-x); } void update(int pos,int val){ while(pos<maxn){ C[pos]+=val; pos+=lowbit(pos); } } int query(int x){ int sum=0; while(x>0){ sum+=C[x]; x-=lowbit(x); } return sum; } int main(){ int n,x,y; int level[maxn]; while(~scanf("%d",&n)){ for(int i=0;i<n;i++){ scanf("%d%d",&x,&y); level[query(++x)]++; update(x,1); } for(int i=0;i<n;i++){ printf("%d\n",level[i]); } } return 0; }