亚洲必赢官网app树状数组的进阶运用(Stars 数星星)

By admin in 亚洲必赢官网app on 2018年10月12日

英文原题

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.

亚洲必赢官网app 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-2018 亚洲必赢手机官网 版权所有