【树状数组】POJ_2352 Stars

本文主要是介绍【树状数组】POJ_2352 Stars，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

题意

给出n个星星，每个星星的等级为它左下角的星星的数量的总和，求出0~n-1等级的星星的数量。

思路

因为题目告诉我们星星的y坐标是按升序来输入的，所以我们只用考虑x坐标，用树状数组找到比当前x坐标小的有几个，然后我们就可以算出每个等级的星星的数量了。

代码

#include<cstdio>
int n,m,tree[32001],level[32001],x,y;
inline int lowbit(int x)
{return x&-x;
}
void insert(int p)
{for (;p<=32001;p+=lowbit(p))//因为坐标的大小最大到32000，所以我们要更新到这里tree[p]++;
}
int find(int a)
{int o=0;for (;a;a-=lowbit(a)) o+=tree[a];return o;
}
int main()
{scanf("%d",&n);for (int i=1;i<=n;i++){scanf("%d%d",&x,&y);level[find(x+1)]++;//因为x可能为0，要防止死循环，find(x+1)代表比x小的星星有多少个insert(x+1);//放进树状数组里}for (int i=0;i<n;i++)printf("%d\n",level[i]);
}

这篇关于【树状数组】POJ_2352 Stars的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---