题目描述

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

如果一个星星的左下方（包含正左和正下）有 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

输入样例：

1
2
3
4
5
6
5
1 1
5 1
7 1
3 3
5 5

输出样例：

1
2
3
4
5
1
2
1
1
0

解题思路

这个题目如果暴力做就是根据每个星星，遍历判断所有星星，最后得到结果，这样时间复杂度就是O(n^2)。但是我们根据题目的输入可以找一下规律。我们发现，题目是根据y递增输入的，y相同按照x递增输入的。所以我们可以发现一个点之后的所有点，他都是在自己右上角的（没有重叠星星）。所以我们可以按照输入顺序，计算每个星星的等级。因为我们当前输入的星星。y一定大于等于前面所有的星星。所以要判断前面的星星是不是在当前星星的右下角，只需要判断前面的星星的x和当前星星的x关系。

这样我们就可以使用树状数组动态维护我们的星星了。需要注意我们这里面坐标会是0。

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
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();
    }
}