POJ2352树状数组
个人NO。1
一开始题意理解有错。
一星星左下边有N颗星星,那它的等级就是N。
一开始理解必须X,Y两个坐标都小于,后来根据样例看了一下只要左下方即可,X,Y坐标都小于等于即可,但不包括星星本身。
#include <iostream> #include <stdio.h> #include <string.h> using namespace std; int lowbit(int x) { return x&-x; } int c[32005]; int x[32005]; int n; int ans[32005]; int visit[32005]; int a[32005]; void add(int x,int y)//后面的所有的值得更新,不包括自身 { while(x<=32005) { c[x]+=y; x+=lowbit(x); } } int sum(int x) { int ret=0; while(x>0) { ret+=c[x]; x-=lowbit(x); } return ret; } int main() { while(scanf("%d",&n)!=EOF) { memset(c,0,sizeof(c)); memset(x,0,sizeof(x)); memset(ans,0,sizeof(ans)); int x,y; for(int i=1;i<=n;i++) { scanf("%d%d",&a[i],&y); if(visit[a[i]+1]==0) { add(a[i]+2,1); visit[a[i]+1]=1; } else add(a[i]+1,1);//c[i]表示比i坐标小的个数 ans[sum(a[i]+1)]++; } for(int i=0;i<n;i++) printf("%d\n",ans[i]); } return 0; } #include <iostream> #include <stdio.h> #include <string.h> using namespace std; int lowbit(int x) { return x&-x; } int c[32005]; int x[32005]; int n; int ans[32005]; int visit[32005]; int a[32005]; void add(int x,int y)//后面的所有的值得更新,不包括自身 { while(x<=32005) { c[x]+=y; x+=lowbit(x); } } int sum(int x) { int ret=0; while(x>0) { ret+=c[x]; x-=lowbit(x); } return ret; } int main() { while(scanf("%d",&n)!=EOF) { memset(c,0,sizeof(c)); memset(x,0,sizeof(x)); memset(ans,0,sizeof(ans)); int x,y; for(int i=1;i<=n;i++) { scanf("%d%d",&a[i],&y); if(visit[a[i]+1]==0) { add(a[i]+2,1); visit[a[i]+1]=1; } else add(a[i]+1,1);//c[i]表示比i坐标小的个数 ans[sum(a[i]+1)]++; } for(int i=0;i<n;i++) printf("%d\n",ans[i]); } return 0; }
补充:软件开发 , C++ ,