【AcWing】蓝桥杯集训每日一题Day18|树状数组|前缀和|1265.数星星(C++)

1265.数星星

题目内容

天空中有一些星星，这些星星都在不同的位置，每个星星有个坐标。
本题采用数学上的平面直角坐标系，即 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坐标增序给出，如果y相同，按x的增序给出，也就是一行一行给每个星星的坐标

N最大时15000，坐标范围最大时32000

如何统计一个星星左下方区域的星星的个数

可以暴力枚举，n^2的计算量
时间限制时0.2s，所以需要控制在2000万以内

• 需要优化
  怎样快速计算当前枚举到的星星左下区域的星星的数量
  设当前星星的坐标是(x，y)，相当于当前现有所有星星当中，横坐标小于等于x的数量
  每次快速的求小于等于x的星星的个数，0~x中所有星星的个数

每次在枚举完之后，需要将当前的星星的横坐标加入到集合当中

两个操作

1. 求某一个前缀中的数的个数
   • 求前缀中数的个数可以转化为求前缀的和
   • 一个数如果出现过多话，就是1，没有出现过就是0
2. 添加一个数
   • 添加一个数，就相当于在某个位置上加1

树状数组可以快速地支持这两个操作
线段树

• 树状数组可以操作的线段树都可以操作，反过来则不一定
  平衡树

树状数组求解的时候下标要从1开始
要先把每一个下标往右平移1，(把每一个x+1)

代码

#include <iostream>
#include <cstring>
#include <algorithm>

using namespace std;

const int N = 15010, M = 32010;

int n;
//tr树状数组，level表示每个等级的星星的数量
int tr[M], level[N];

//树状数组模板
int lowbit(int x)
{
	//返回的是x的二进制表示当中最后一位1
	return x & -x;
}

void add (int x, int v)  //位置x加c
{
	for (int i = x; i <= M; i += lowbit(i)) 
		tr[i] += v;
}

int query(int x)  //返回前x个数的和
{
	int res = 0;
	for (int i = x; i; i -= lowbit(i)) 
		res += tr[i];
	return res;
}

int main()
{
	//读入星星的数量
	scanf("%d", &n);
	//依次读入每个星星
	for (int i = 0; i < n; i ++)
	{
		int x, y;
		scanf("%d%d", &x, &y);
		//当前的等级
		x ++;
		//统计一下1~x中的数的总和
		int t = query(x);
		//这个等级的星星数+1
		level[t] ++;
		//把当前数加到树状数组当中
		add(x, 1);
	}

	for (int i = 0; i < n; i ++)
		printf("%d\n", level[i]);

	return 0;
}