和之前那个Japan 那题差不多,而且这个还给排好序了。。。赞!
这样的话 ,只要比较x坐标, 因为y是排好的,后面的点不会对前面的点产生影响。
这样,还是求逆序数。
AC Memory : 908 KB Time : 391 ms
代码:
#include <iostream> #include <cstdio> #include <cstring> using namespace std; int c[32005]; int res[32005]; int lowbit(int x) { return x&(-x); } void update(int i,int val) { while(i<=32002) { c[i]+=val; i += lowbit(i); } } int sum(int i) { int s= 0; while(i>0) { s+=c[i]; i-=lowbit(i); } return s; } int main() { int n,x,y; scanf("%d",&n); memset(c,0,sizeof(c)); memset(res,0,sizeof(res)); for(int i = 0;i<n;++i) { scanf("%d%d",&x,&y); ++res[sum(x+1)]; update(x+1,1); } for(int i = 0;i<n;++i) { printf("%d\n",res[i]); } return 0; }