分析:由于输入数据是以y为第一关键递增输入,以x为第二关键字递增输入,因此,可以直接对x用一维树状数组。
#include<stdio.h> #include<string.h> int count[32005]; int c[32005]; int lowbit(int x) { return x&(-x); } void change(int x) { int i; for(i=x;i<32005;i+=lowbit(i)) c[i]++; } int sum(int x) { int i,sum=0; for(i=x;i>0;i-=lowbit(i)) sum+=c[i]; return sum; } int main() { memset(count,0,sizeof(count)); memset(c,0,sizeof(c)); int x,y,i,n; scanf("%d",&n); for(i=0;i<n;i++) { scanf("%d %d",&x,&y); x++;//不能少了这行,否则出现x=0时change会出现死循环,导致超时 count[sum(x)]++; change(x); } for(i=0;i<n;i++) printf("%d\n",count[i]); return 0; }