十八 1265. 数星星 (树状数组)

1265. 数星星 (树状数组)

思路：本题要统计每个星星左下角星星的数目，由于星星按y坐标增序给出，y坐标相同的按x坐标增序给出，所以不用关注y，可以视作每个x位置有几颗星星就为几的数组，每次统计左侧前缀和，再将当前计算的星星x位置数加一，使用树状数组（推荐视频：五分钟丝滑动画讲解 | 树状数组）结构可以支持这种操作，因为树状数组从1开始，所以所有的x坐标都需要加一。同时因为本题读写次数很多，需要使用BufferedReader和BufferedWriter防止超时。

import java.util.*;
import java.io.*;

public class Main {
    private static int N = 32010, M = 15010;
    private static int[] tr = new int[N], level = new int[M];
    
    private static int lowbit(int x) {
        return x & -x;
    }
    
    private static void add(int x) {
        for (int i = x; i < N; i += lowbit(i)) {
            tr[i]++;
        }
    }
    
    private static int sum(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 IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
        int n = Integer.parseInt(br.readLine());
        for (int i = 0; i < n; i++) {
            String[] s = br.readLine().split(" ");
            int x = Integer.parseInt(s[0]);
            x++;
            level[sum(x)]++;
            add(x);
        }
        for (int i = 0; i < n; i++) {
            bw.write(level[i] + "\n");
        }
        bw.flush();
    }
}