数星星 Stars 题解

题目链接

分析

一道树状数组，但坑点比较多。。。
首先在草稿纸上画图可以得知：星星的等级与\(x\)无关，至于\(y\)的大小有关，于是我们可以根据输入顺序一一将其插入树状数组进行维护，此星星的等级其实就是在插入前以\(1\)~星星的\(y\)的星星数量和。

注意

星星的坐标是从\((0, 0)\)开始存，但树状数组不能够维护，所以要提前将所有星星的\(x\)加上一。(如果在求和函数中把限度跳到0就会卡死循环我就错了)

代码

#include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm>
using namespace std;
const int MAXN = 3e5 + 5;

int x[MAXN], n, m, star[MAXN], t[MAXN];
int bit[MAXN];

int lowbit(int x) {
	return x & (-x);
}

void update(int k, int x) {
	for (int i = k; i <= MAXN; i += lowbit(i)) {
		bit[i] += x;
	}
}

int Sum(int k) {
	int ans = 0;
	for (int i = k; i; i -= lowbit(i)) {
		ans += bit[i];
	} 
	return ans;
} 

int main() {
//	freopen("star.in", "r", stdin);
//	freopen("star.out", "w", stdout);
	scanf ("%d", &n);
	for (int i = 1, y; i <= n; i++) {
		scanf ("%d %d", &x[i], &y);
		++x[i];
		m = max(m, x[i]);
	}
	for (int i = 1; i <= n; i++) {
		star[Sum(x[i])] ++;
		update(x[i], 1);
	}
	for (int i = 0; i < n; i++) {
		printf ("%d\n", star[i]);
	}
	return 0;
}