【HDU 1541】树状数组（入门题）

题目链接：http://acm.hdu.edu.cn/showproblem.php?pid=1541

题目大意：开始输入一个n（表示有n颗星星）。接下来n行，每行输入一个x，y，代表星星的坐标，注意y是递增输入。求各阶段星星的等级（阶段分为0~n-1）有多少，星星等级数计算方法为本星星左下角的有的星星个数。

 1 #include <iostream>
 2 #include <cstdio>
 3 #include <algorithm>
 4 #include <cstring>
 5 using namespace std;
 6 
 7 const int maxn=32050;
 8 int  bit[maxn];
 9 int  level[maxn];
10 int  n;
11 
12 int lowbit(int x)
13 {
14     return x&((x)xor(x-1)); //等价于x&(-x)
15 }
16 
17 void add(int x,int val)   //用树状数组对后面节点更新
18 {
19     while(x<maxn)
20     {
21         bit[x]+=val;
22         x+=lowbit(x);
23     }
24 }
25 
26 int sum(int x)
27 {
28     int rank=0;   //rank代表星星的等级，即它的左下角有的星星个数
29     while(x>0)
30     {
31         rank+=bit[x];
32         x-=lowbit(x);
33     }
34     return rank;
35 }
36 
37 int main()
38 {
39     int   x, y;
40     while(scanf("%d",&n)!=EOF)
41     {
42         memset(bit,0,sizeof(bit));
43         memset(level,0,sizeof(level));
44         for(int i=0; i<n; i++)
45         {
46             scanf("%d%d",&x,&y);
47             level[sum(++x)]++;  //此阶段等级加1
48             add(x,1);
49         }
50         for(int i=0; i<n; i++)
51             printf("%d\n",level[i]);
52     }
53     return 0;
54 }

【HDU 1541】 树状数组（入门题）

【HDU 1541】树状数组（入门题）