树状数组的进阶运用

By admin in 亚洲必赢官网app on 2019年2月5日

英文原题

Problem
Description

Astronomers
often examine star maps where stars are represented by points on a plane
and each star has Cartesian coordinates. Let the level of a star be an
amount of the stars that are not higher and not to the right of the
given star. Astronomers want to know the distribution of the levels of
the stars.

图片 1

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.

Input

The first line
of the input file contains a number of stars N (1<=N<=15000). The
following N lines describe coordinates of stars (two integers X and Y
per line separated by a space, 0<=X,Y<=32000). There can be only
one star at one point of the plane. Stars are listed in ascending order
of Y coordinate. Stars with equal Y coordinates are listed in ascending
order of X coordinate.

Output

The output
should contain N lines, one number per line. The first line contains
amount of stars of the level 0, the second does amount of stars of the
level 1 and so on, the last line contains amount of stars of the level
N-1.

Sample
Input

5 1 1 5 1 7 1
3 3 5 5

Sample
Output

1 2 1 1
0

翻译题意

天史学家把苍天的每颗星星都画在一个平面上,并给定每颗的坐标。同时把个别左下方(包括横坐标或者纵坐标一样的)的有数数目定义为该星星的阶段。天史学家想明白星星等级的遍布。
比如说上图中,5号星星的阶段为3(左下方的有限为1,2,4),2号与4号星星等级为1。上图中等级为0的不难有1颗,等级为1的星星点点有2颗,等级为2的少数有1颗,等级为3的个别有1颗。
请写一个程序总计显示器上每一个品级的星星数。

有心人审题之后,发现是树状数组,因为输入的xy的值是板上钉钉的,所以只需求建立c[x]代表横坐标小于等于x的符合须要的点有多少个,运用到树状数组的基础知识,计算出即可。

下边给出代码

 1 //树状数组基本框架的搭建(维护和查询都是O(lgn)的复杂度) 
 2 #include<iostream>
 3 #include<cstdio>
 4 #include<cstdlib>
 5 #include<cstring>
 6 #include<string>
 7 using namespace std;
 8 int n,a,b;
 9 int c[40000],ans[40000];//注意数组的大小
10 
11 int lowbit(int k)
12 {
13      return k&(-k);
14      
15 }
16 int add(int k,int num)
17 {
18     while(k<=32010)//此处的32010应为n的最大值+2
19     {
20          c[k]+=num;
21          k+=lowbit(k);
22     }
23 }
24 int sum(int k)
25 {
26     int Sum=0;
27     while(k>0)
28     {
29         Sum+=c[k];
30         k-=lowbit(k);
31     }
32     return Sum;
33 }
34 
35 
36 int main()
37 {
38      cin>>n;
39      for(int i=1;i<=n;i++)
40      {
41         cin>>a>>b;
42         a=a+1;//树状数组的下标需要从1开始,而数据从0开始,故此+1;
43         ans[sum(a)]++;
44         add(a,1); 
45      }
46      for(int i=0;i<n;i++)
47        cout<<ans[i]<<endl;
48     return 0;
49 }

 

发表评论

电子邮件地址不会被公开。 必填项已用*标注

网站地图xml地图
Copyright @ 2010-2019 亚洲必赢手机官网 版权所有