AcWing 1265. 数星星(每日一题)

简介: AcWing 1265. 数星星(每日一题)
原题链接:1265. 数星星 - AcWing题库

天空中有一些星星,这些星星都在不同的位置,每个星星有个坐标。

本题采用数学上的平面直角坐标系,即 x 轴向右为正方向,y 轴向上为正方向。

如果一个星星的左下方(包含正左和正下)有 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 级的星星的数目。

数据范围

1≤N≤15000,

0≤x,y≤32000

输入样例:

5
1 1
5 1
7 1
3 3
5 5

输出样例:

1
2
1
1
0
解题思路:

看这张图片就是树状数组,题目中又按照y升序指出,要求统计左下面的所有点,直接树状数组统计即可,此题暴力可不过,因为此题要求在0.2s内,使用树状数组可以做到每步O(logN)的时间复杂度。具体开一个统计等级个数数组,每输入一个点,看一看它前面有多少个数,就是多少个等级,每有一个等级,计数数组++即可。

#include<iostream>
using namespace std;
const int N=32005,M=15005;
int n,x,y;
int a[N],c[N];
int lowbit(int x){//二进制中最后一位1
  return x&(-x);
}
void add(int x,int k){//单点修改数值
  for(int i=x;i<=N;i+=lowbit(i)){
    c[i]+=k;
  }
}
int query(int x){//1~x的区间和
  int sum=0;
  for(int i=x;i>0;i-=lowbit(i)){//逆序
    sum+=c[i];
  }
  return sum;
}
int main(){
  cin>>n;
  for(int i=1;i<=n;i++){
    cin>>x>>y;
    x++;//下标必须从一开始
    int t=query(x);//前面有几个就是等级为几
    a[t]++;
    add(x,1);//加入到树状数组
  }
  for(int i=0;i<n;i++){//最后输出一下等级个数
    cout<<a[i]<<endl;
  }
  return 0;
}
总结:

此题理解了题意,直接利用树状数组模板就可以解决,难点在理解上,树状数组不用去懂得原理,背好模板,记得在单点修改和区间查询上时间复杂度很低即可。树状数组时一个重要的数据结构很好用,比线段树简单,可以学一下,文章尚有不足,有错误请各位指出。

相关文章
|
2月前
【LeetCode-每日一题】移动零
【LeetCode-每日一题】移动零
27 1
AcWing 562. 壁画(每日一题)
AcWing 562. 壁画(每日一题)
LeetCode】每日一题(4)
LeetCode】每日一题(4)
45 0
【LeetCode】每日一题(3)
【LeetCode】每日一题(3)
65 0
|
算法 C语言 索引
每日一题:LeetCode-283. 移动零
每日一题:LeetCode-283. 移动零
acwing刷题(一)
acwing刷题(一)
92 0
【LeetCode】每日一题(5)
【LeetCode】每日一题(5)
54 0
|
算法
【LeetCode】每日一题(1)
【LeetCode】每日一题(1)
67 0
【LeetCode】每日一题(2)
【LeetCode】每日一题(2)
65 0
|
存储
每日一题——螺旋矩阵
每日一题——螺旋矩阵