19728 拼十字
⭐️难度：中等
🌟考点：树状数组、省赛、2024
📖
📚
import java.io.*;
import java.util.*;public class Main {static class FenwickTree {int n;int[] tree;public FenwickTree(int n) {this.n = n;tree = new int[n + 1];}int lowbit(int i) {return i & -i;}void add(int i, int val) {for (; i <= n; i += lowbit(i)) {tree[i] += val;}}int preSum(int i) {int ret = 0;for (; i > 0; i -= lowbit(i)) {ret += tree[i];}return ret;}int rangeSum(int l, int r) {return preSum(r) - preSum(l - 1);}}static int maxn = 100010;static int ans = 0;static int mod = (int) 1e9 + 7;public static void main(String[] args) {Scanner sc = new Scanner(System.in);int n = sc.nextInt();List<int[]> arr = new ArrayList<>();// 读入所有的矩形for (int i = 0; i < n; i++) {int l = sc.nextInt(); // 长int w = sc.nextInt(); // 宽int c = sc.nextInt(); // 颜色arr.add(new int[]{l, w, c});}// 对矩形进行排序，l升序，然后w升序arr.sort((o1, o2) -> {if (o1[0] != o2[0]) return Integer.compare(o1[0], o2[0]);else return Integer.compare(o1[1], o2[1]);});// 建立三种颜色对应的树状数组FenwickTree[] tree = new FenwickTree[3];for (int i = 0; i < 3; i++) tree[i] = new FenwickTree(maxn);// 然后枚举排序好的arrfor (int[] a : arr) {int l = a[0];int w = a[1];int c = a[2];for (int i = 0; i < 3; i++) {if (c == i) continue; // 相同颜色被排除掉ans = (ans + tree[i].rangeSum(w + 1, maxn)) % mod; // 累加答案}tree[c].add(w, 1); // 更新树状数组}System.out.println(ans);}
}
