题目描述
输入样例
5
1 1
5 1
7 1
3 3
5 5
输出样例
1
2
1
1
0
基本思路
1.星星按y坐标增序给出,y坐标相同的按x坐标增序给出
2.由此可知,对于在当前星星之前给出的星星y坐标一定小于等于当前星星,所以y坐标一定满足要求,只需看x坐标是否满足即可
3.而且不会有星星重叠,因此在当前星星之后给出的星星不用考虑,因为x和y坐标必定有一个不满足要求
4.这样就可以简化成一维,然后规定树状数组的下标为星星的x坐标,树状数组里存的值表示横坐标为x的星星个数
5.所以,对树状数组tr求前缀和就可以得到当前星星的级数
c++代码
#include<iostream>
#include<algorithm>
#include<string>
using namespace std;
const int N = 32010;
//tr[i]表示横坐标为i的星星的个数,level[i]表示级数为i的星星个数
int tr[N], level[N];
int n;
int lowbit(int x) {
return x & -x;
}
void add(int x) {
for (int i = x; i < N; i += lowbit(i)) tr[i]++;
}
int sum(int x) {
int res = 0;
for (int i = x; i > 0; i -= lowbit(i)) res += tr[i];
return res;
}
int main() {
cin >> n;
for (int i = 0; i < n; i++) {
int x, y;
cin >> x >> y;
x++;//因为树状数组的下标一般是从1开始的
level[sum(x)]++;//sum(x)求出横坐标小于等于x的星星个数,即当前星星的级数
add(x);//将当前星星加入到树状数组中,让横坐标为x的星星个数加1即可
}
for (int i = 0; i < n; i++) cout << level[i] << endl;
return 0;
}