poj 2352 stars 树状数组
这个题目刚开始没读懂,以为就是二维树状数组求上角矩阵和。
其实根本不用二维,因为数据已经有序,每次求的时候都是X方向上的比较。不过误打误撞也写了个离散化的代码。
WA:
#include<cstdio> #include<string> #include<iostream> #include<map> #include<iterator> using namespace std; #define N 15000 int c[N][N],n,mm; int d[N]; int a[N],b[N]; struct m{ bool operator()(const int &a,const int &b) { return a<b; } }; map<int,int,m> mp; int lowbit(int x) {return -x&x;} void update(int r,int l,int num) { int i,j; for(i=r;i<=mm;i+=lowbit(i)) for(j=l;j<=mm;j+=lowbit(j)) c[i][j]+=num; } int sum(int r,int l) { int ans=0; int i,j; for(i=r;i>0;i-=lowbit(i)) for(j=l;j>0;j-=lowbit(j)) ans+=c[i][j]; return ans; } int main() { int i,j,k; while(~scanf("%d",&n)) { memset(c,0,sizeof(c)); memset(d,0,sizeof(d)); for(i=1;i<=n;i++) { scanf("%d%d",a+i,b+i); a[i]++;b[i]++; mp[a[i]]++; mp[b[i]]++; } map<int,int,m>::iterator it=mp.begin(); for(i=1;it!=mp.end();it++,i++) it->second=i; mm=i-1; for(i=1;i<=n;i++) { a[i]=mp[a[i]]; b[i]=mp[b[i]]; update(b[i],a[i],1); } for(i=1;i<=n;i++) { k=sum(b[i],a[i]); d[k-1]++; } for(i=0;i<n;i++) printf("%d\n",d[i]); } return 0; }
AC:
#include<cstdio> #include<string> #include<iostream> #include<map> #include<iterator> using namespace std; #define N 150001 int c[N],n,mm; int d[N]; int a[N]; int lowbit(int x) {return -x&x;} void update(int r,int num) { int i; for(i=r;i<=N;i+=lowbit(i)) c[i]+=num; } int sum(int r) { int ans=0; int i; for(i=r;i>0;i-=lowbit(i)) ans+=c[i]; return ans; } int main() { int i,j,k; while(~scanf("%d",&n)) { memset(c,0,sizeof(c)); memset(d,0,sizeof(d)); for(i=1;i<=n;i++) { scanf("%d%d",a+i,&j); a[i]++; update(a[i],1); d[sum(a[i])-1]++; } for(i=0;i<n;i++) printf("%d\n",d[i]); } return 0; }
郑重声明:本站内容如果来自互联网及其他传播媒体,其版权均属原媒体及文章作者所有。转载目的在于传递更多信息及用于网络分享,并不代表本站赞同其观点和对其真实性负责,也不构成任何其他建议。