HDU 1541 star (树状数组)
Stars
Time Limit: 2000/1000 MS (Java/Others) Memory Limit: 65536/32768 K (Java/Others)
Total Submission(s): 5400 Accepted Submission(s): 2133
For example, look at the map shown on the figure above. Level of the star number 5 is equal to 3 (it‘s formed by three stars with a numbers 1, 2 and 4). And the levels of the stars numbered by 2 and 4 are 1. At this map there are only one star of the level 0, two stars of the level 1, one star of the level 2, and one star of the level 3.
You are to write a program that will count the amounts of the stars of each level on a given map.
题目大意:
给你n个点,这n个点的输入是按照y递增的顺序输入的,让你求出每个点左下角有多少个点。
解题思路:
看到后,就想到了BIT,因为至少有15000个点需要我们来维护,如果每次插入一个点,然后再去用O(n^2)去处理的话,肯定会很慢,于是我们就想到了
用BIT来维护了。但是,BIT中的tree[]必须是从1开始的,所以我们必须要对于所有的横坐标都预处理下,相当于把坐标系向左平移一个单位,这样一来,我们就不用担心x=0,的情况了,一开始tree[]中的所有元素都是0,而这个数组的长度就是x的最大值,因为我们可以假设最坏的情况下,所有的x的值都有可能取到。然后,我们每次新增加一个点,我们就去判断这个点的前面有多少个点,因为y是按照递增的顺序插入的,所以已经满足了左下角的要求了,每次插入一个点,就在相应的x上加1。
最后统计每个x上的点的个数就好了。。。
代码:
# include<cstdio> # include<iostream> # include<fstream> # include<algorithm> # include<functional> # include<cstring> # include<string> # include<cstdlib> # include<iomanip> # include<numeric> # include<cctype> # include<cmath> # include<ctime> # include<queue> # include<stack> # include<list> # include<set> # include<map> using namespace std; const double PI=4.0*atan(1.0); typedef long long LL; typedef unsigned long long ULL; # define inf 999999999 # define MAX 32000+5 int ans[MAX]; int tree[MAX]; int read( int pos ) { int sum = 0; while ( pos > 0 ) { sum+=tree[pos]; pos-=pos&(-pos); } return sum; } void update( int pos,int val ) { while ( pos <= MAX ) { tree[pos]+=val; pos+=pos&(-pos); } } int main(void) { int n; while ( cin>>n ) { memset(tree,0,sizeof(tree)); memset(ans,0,sizeof(ans)); int x,y; for ( int i = 0;i < n;i++ ) { cin>>x>>y; x++; ans[read(x)]++; update(x,1); } for ( int i = 0;i < n;i++ ) { cout<<ans[i]<<endl; } } return 0; }
郑重声明:本站内容如果来自互联网及其他传播媒体,其版权均属原媒体及文章作者所有。转载目的在于传递更多信息及用于网络分享,并不代表本站赞同其观点和对其真实性负责,也不构成任何其他建议。