树状数组

特殊瓷器(相似题目)

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

public class Main {
    static BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
    static PrintWriter out = new PrintWriter(System.out);
    static final int N = 32010;
    static int[] tr = new int[N], grade = new int[N];
    static int n;

    public static void main(String[] args) throws IOException {
        n = Integer.parseInt(br.readLine());
        for (int i = 0; i < n; i++) {
            String[] str = br.readLine().split(" ");
            int x = Integer.parseInt(str[0]);
            grade[query(++x)]++;
            add(x, 1);
        }

        for (int i = 0; i < n; i++) out.println(grade[i]);
        out.flush();
    }

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

    static void add(int idx, int c) {
        //添加的横坐标的范围不是n而是N(要注意)
        for (int i = idx; i < N; i += lowbit(i)) tr[i] += c;
    }

    static int query(int r) {
        int res = 0;
        for (int i = r; i > 0; i -= lowbit(i)) res += tr[i];
        return res;
    }
}

特别写法,对于大坐标的离散化(权当复习)

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

public class Main {
    static FastReader sc = new FastReader();
    static PrintWriter out = new PrintWriter(System.out);

    static final int N = 15010;
    static int[] x, y, tr = new int[N], g = new int[N];
    static ArrayList<Pair> pp = new ArrayList<>();
    static int n;

    public static void main(String[] args) throws IOException {
        n = sc.nextInt();
        x = new int[n];
        y = new int[n];
        for (int i = 0; i < n; i++) {
            x[i] = sc.nextInt();
            y[i] = sc.nextInt();
        }
        discrete(x);
        discrete(y);
        for (int i = 0; i < n; i++) {
            pp.add(new Pair(x[i], y[i]));
        }

        pp.sort((o1, o2) -> {
            if (o1.y != o2.y) {
                return o1.y - o2.y;
            }
            return o1.x - o2.x;
        });
        for (int i = 0; i < n; i++) {
            int x = pp.get(i).x;
            g[sum(x)]++;
            add(x, 1);
        }

        for (int i = 0; i < n; i++) {
            out.println(g[i]);
        }
        out.flush();
    }

    static void add(int x, int v) {
        for (int i = x; i < N; i += lowbit(i)) {
            tr[i] += v;
        }
    }

    static int sum(int r) {
        int res = 0;
        for (int i = r; i > 0; i -= lowbit(i)) {
            res += tr[i];
        }
        return res;
    }

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

    static void discrete(int[] x) {
        int[] unique = Arrays.stream(x).sorted().distinct().toArray();
        for (int i = 0; i < n; i++) {
            x[i] = Arrays.binarySearch(unique, x[i]) + 1;
        }
    }
}

class Pair{
    int x, y;
    public Pair(int x, int y) {
        this.x = x;
        this.y = y;
    }

    public int getY() {
        return y;
    }
}

class FastReader {
    BufferedReader br;
    StringTokenizer st;

    public FastReader() {
        br = new BufferedReader(new InputStreamReader(System.in));
    }

    String next() {
        while (st == null || !st.hasMoreTokens()) {
            try {
                st = new StringTokenizer(br.readLine(), " ");
            } catch (Exception e) {
                throw new RuntimeException();
            }
        }
        return st.nextToken();
    }

    int nextInt() {
        return Integer.parseInt(next());
    }
}