这个题那次切选拔赛的时候做出来的。。。但是竟然忘记了。。。第一次CE了太疏忽了。。。。
题意:按照y的升序给出数据,y相等时按照x的升序给出,然后再图上就是看某一个点它的左下方有几个点则这个点就在哪个level上,最后输出每个level的点数
其实就是求所给的x,它的等级就是已经输入的坐标的横坐标范围在[0,x]上的点的总数。
#include <cstdio> #include <cstdlib> #include <algorithm> #include <string.h> using namespace std; int n; const int maxn=32010; int c[maxn]; int lev[maxn]; int lowbit(int i) { return i&(-i); } void update(int x,int val) { while(x<maxn) { c[x]+=val; x+=lowbit(x); } } int sum(int i) { int ans=0; while(i>0) { ans+=c[i]; i-=lowbit(i); } return ans; } int main() { int x,y; while(~scanf("%d",&n)) { memset(c,0,sizeof(c)); memset(lev,0,sizeof(lev)); for(int i=0;i<n;i++) { scanf("%d%d",&x,&y); x++; lev[sum(x)]++; update(x,1); } for(int i=0;i<n;i++) { printf("%d\n",lev[i]); } } }