首页 > 其他 > 详细

数星星

时间:2019-01-20 11:17:49      阅读:215      评论:0      收藏:0      [点我收藏+]

天空中有一些星星,这些星星都在不同的位置,每个星星有个坐标。如果一个星星的左下方(包含正左和正下)有 k 颗星星,就说这颗星星是 k 级的。

技术分享图片

例如,上图中星星 5 是 3 级的(1,2,4 在它左下),星星 2,4 是 1 级的。例图中有 1 个 0 级,2 个 1 级,1 个 2 级,1 个 3 级的星星。

给定星星的位置,输出各级星星的数目。

一句话题意 \  给定 n 个点,定义每个点的等级是在该点左下方(含正左、正下)的点的数目,试统计每个等级有多少个点。

输入格式

第一行一个整数 N,表示星星的数目;
接下来 N行给出每颗星星的坐标,坐标用两个整数 x,y 表示;
不会有星星重叠。星星按 y 坐标增序给出,y 坐标相同的按 x 坐标增序给出。

输出格式

N 行,每行一个整数,分别是 0 级,1 级,2 级,……,N?1 级的星星的数目。

样例

样例输入

5
1 1
5 1
7 1
3 3
5 5

样例输出

1
2
1
1
0

数据范围与提示

对于全部数据,1N1.5×10^4,0x,y3.2×10^4。

________________________________________________________________________________________________

树状数组,比较简单。

注意,星星的坐标要从0开始。

________________________________________________________________________________________________

技术分享图片
 1 #include<bits/stdc++.h>
 2 using namespace std;
 3 const int maxn=15010;
 4 const int maxm=32010;
 5 int sz[maxm],n;
 6 int ans[maxn];
 7 inline int lowbit(int x)
 8 {
 9     return x&-x;
10 }
11 void update(int x)
12 {
13     for(int i=x;i<maxm;i+=lowbit(i))++sz[i];
14 }
15 int get(int x)
16 {
17     int ans=0;
18     for(int i=x;i;i-=lowbit(i))ans+=sz[i];
19     return ans;
20 }
21 int main()
22 {
23     scanf("%d",&n);
24     for(int x,y,i=0;i<n;++i)
25     {
26         scanf("%d%d",&x,&y);
27         ++x,++y;
28         ans[get(x)]++;
29         update(x);
30     }
31     for(int i=0;i<n;++i)printf("%d\n",ans[i]);
32     return 0;
33 }
View Code

 

数星星

原文:https://www.cnblogs.com/gryzy/p/10293999.html

(0)
(0)
   
举报
评论 一句话评论(0
关于我们 - 联系我们 - 留言反馈 - 联系我们:wmxa8@hotmail.com
© 2014 bubuko.com 版权所有
打开技术之扣,分享程序人生!