数星星(树状数组模板题)

简介: 数星星(树状数组模板题)

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


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


7532b929e2f6552462eb109af9902338.png


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


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


输入格式


第一行一个整数 N,表示星星的数目;

接下来 N 行给出每颗星星的坐标,坐标用两个整数 x,y表示;

不会有星星重叠。星星按 y 坐标增序给出,y 坐标相同的按 x 坐标增序给出。


输出格式

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


样例

Input Output
1. 5
2. 1 1
3. 5 1
4. 7 1
5. 3 3
6. 5 5
1. 1
2. 2
3. 1
4. 1
5. 0


有事你就q我;QQ2917366383


学习算法


我们可以知道这个可以暴力但是可能会超限,所以我们用树状数组;下面是ac代码,重点处都备注好了。

#include<cstdio>
const int maxn=1e6+7;//大家不要用暴力解法,有时候会卡数据 
int c[maxn], b[maxn];   
int n, x, y;
int Lowbit(int x){
  return x&(-x);
}
void update(int x, int y){
  for(int i = x; i <= 32001; i+=Lowbit(i))// 将x位置的树状数组都加1 
    c[i] += y;
}
int sum(int x){
  int sumn=0;
  for(int i = x; i > 0; i-=Lowbit(i))//累加星星 
    sumn += c[i];
  return sumn;
}
int main(){
  scanf("%d", &n); 
  for(int i = 1; i <= n; i++){
    scanf("%d%d", &x,&y);//题目说了是按照顺序排的,所以我们可以直接用 
      b[sum(x+1)]++;//将sum(x+1)的值比做有几个星星 
          update(x+1, 1); //统计星星个数 
  //顺便提一下这里x+1是为了防止在sum(1)时报错 ,加1不影响结果 
  } 
  for(int i = 0; i < n; i++)
    printf("%d\n", b[i]); 
  return 0;//此处掌声 
}
目录
打赏
0
0
0
0
8
分享
相关文章
poj 1990 MooFest 树状数组
题意就是有N头牛,每头牛都有一个坐标和声调值(x, v),两头牛之间通讯要花费的能量是他们的距离乘以最大的一个音调值,现在要任意两头牛之间都相互通讯一次,求总共需要花费多少能量?
58 0
第十二届蓝桥杯《杨辉三角》-二分法
第十二届蓝桥杯《杨辉三角》-二分法
119 0
每日一题——三数之和(双指针)
每日一题——三数之和(双指针)
每日一题——四数之和(双指针解法)
每日一题——四数之和(双指针解法)
日拱算法:双指针解决三数、四数之和
本篇带来两道相似的、有递进关系的“双指针”算法题。 冲就完事了吼~~

热门文章

最新文章

AI助理

你好,我是AI助理

可以解答问题、推荐解决方案等