题目描述
天空中有一些星星,这些星星都在不同的位置,每个星星有个坐标。
如果一个星星的左下方(包含正左和正下)有 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
解题思路
这个题目如果暴力做就是根据每个星星,遍历判断所有星星,最后得到结果,这样时间复杂度就是O(n^2)。但是我们根据题目的输入可以找一下规律。我们发现,题目是根据y递增输入的,y相同按照x递增输入的。所以我们可以发现一个点之后的所有点,他都是在自己右上角的(没有重叠星星)。所以我们可以按照输入顺序,计算每个星星的等级。因为我们当前输入的星星。y一定大于等于前面所有的星星。所以要判断前面的星星是不是在当前星星的右下角,只需要判断前面的星星的x和当前星星的x关系。
这样我们就可以使用树状数组动态维护我们的星星了。需要注意我们这里面坐标会是0。
代码
import java.io.*;
import java.util.*;
class Main{
public static int N = 15001,M = 32010;
public static int[] tr = new int[M],a = new int[N];
public static BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
public static BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
public static int lowbit(int x){
return (-x) & x;
}
public static void insert(int x,int k){
for(int i = x;i < M;i += lowbit(i)) tr[i] += k;
}
public static int get(int x){
int res = 0;
for(int i = x;i > 0;i -= lowbit(i)) res += tr[i];
return res;
}
public static void main(String[] args)throws Exception{
int n = Integer.parseInt(br.readLine());
for(int i = 1;i <= n;i++){
String[] s1 = br.readLine().split(" ");
int x = Integer.parseInt(s1[0]) + 1;
a[get(x)]++;
insert(x,1);
}
for(int i = 0;i < n;i++) bw.write(a[i]+"\n");
bw.flush();
}
}