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

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

天空中有一些星星,这些星星都在不同的位置,每个星星有个坐标。如果一个星星的左下方(包含正左和正下)有 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
分享
相关文章
C/C++每日一练(20230510) 编辑距离、多数元素、数列累和
C/C++每日一练(20230510) 编辑距离、多数元素、数列累和
94 0
日拱算法:双指针解决三数、四数之和
本篇带来两道相似的、有递进关系的“双指针”算法题。 冲就完事了吼~~
LeetCode 周赛 342(2023/04/23)容斥原理、计数排序、滑动窗口、子数组 GCB
前天刚举办 2023 年力扣杯个人 SOLO 赛,昨天周赛就出了一场 Easy - Easy - Medium - Medium 的水场,不得不说 LeetCode 是懂礼数的 😁。 接下来,请你跟着小彭的思路,一步步将问题做难,再将问题做简单。
98 0
代码随想录刷题|LeetCode 1143.最长公共子序列 1035.不相交的线 53. 最大子序和 动态规划
代码随想录刷题|LeetCode 1143.最长公共子序列 1035.不相交的线 53. 最大子序和 动态规划
代码随想录刷题|LeetCode 1143.最长公共子序列 1035.不相交的线 53. 最大子序和 动态规划
蓝桥杯第十三讲--树状数组与线段树【例题】(二)
蓝桥杯第十三讲--树状数组与线段树【例题】
162 0
蓝桥杯第十三讲--树状数组与线段树【例题】(二)

热门文章

最新文章