首页 > 代码库 > POJ 2352 Stars 树状数组
POJ 2352 Stars 树状数组
题目大意:给出y值升序的一些点,定义一个点的level值为它左下方的点的数量,求每一个level有多少个点。
思路:由于y值是升序的,那么后面的点只要判断是否x值比前面的大就行了。那么就用树状数组维护。
CODE:
#include <cstdio> #include <cstring> #include <iostream> #include <algorithm> #define MAX 50000 using namespace std; int cnt,fenwick[MAX]; int ans[MAX]; inline void Initialize(); inline void Fix(int x); inline int GetSum(int x); int main() { while(scanf("%d",&cnt) != EOF) { Initialize(); for(int x,y,i = 1;i <= cnt; ++i) { scanf("%d%d",&x,&y); x++; Fix(x); ans[GetSum(x)]++; } for(int i = 1;i <= cnt; ++i) printf("%d\n",ans[i]); } return 0; } inline void Initialize() { memset(fenwick,0,sizeof(fenwick)); memset(ans,0,sizeof(ans)); } inline void Fix(int x) { for(;x < MAX;x += x&-x) fenwick[x]++; } inline int GetSum(int x) { int re = 0; for(;x;x -= x&-x) re += fenwick[x]; return re; }
POJ 2352 Stars 树状数组
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。