当前位置: 代码迷 >> 综合 >> POJ 2352 Stars(树状数组,查数)
  详细解决方案

POJ 2352 Stars(树状数组,查数)

热度:14   发布时间:2024-01-22 01:53:41.0

题意:

二维平面给定n个点(任意两个点不重合)的坐标,然后要你输出每个点的“等级“。每个点的等级是它的左下放的点个数(包括正下放和正左方的点)。最后输出每个等级的点的个数。

题解:

任意两个点不会重叠,且给出点的顺序是:按Y坐标上升的顺序来给出,如果Y相同  就按X上升的顺序给出。

给出的顺序是完美的,只需要找左边有多少个比当前X小的就可以了。树状数组查数基本应用!

#include<cstdio>
#include<iostream>
#include<algorithm>
#include<cstring>using namespace std;const int maxn=32111;int c[maxn];
int level[maxn];int lowbit(int x)
{return x & -x;
}int sum(int x)
{int res=0;while(x>0){res += c[x];x -= lowbit(x);}return res;
}void add(int x,int v)
{while(x<maxn){c[x] += v;x+=lowbit(x);}
}int main()
{int n;while(cin>>n){memset(c,0,sizeof c);memset(level,0,sizeof level);for(int i=0;i<n;i++){int x,y;scanf("%d%d",&x,&y);x++;level[sum(x)]++;add(x,1);}for(int i=0;i<n;i++)printf("%d\n",level[i]);}
}