返回题解分享
讨论 / 题解分享/ 帖子详情

拼十字(编程题) - 题解

import java.io.PrintWriter;
import java.util.*;
 
public class Main {
    static int N = 100010;
    static long mod = (int) 1e9 + 7;
    static long[] a = new long[N];
    static long[] b = new long[N];
    static long[] c = new long[N];
 
    static int lowbit(int x) {
        return x & -x;
    }
 
    static void add(long[] tr, int x, long v) {
        for (int i = x; i < N; i += lowbit(i)) tr[i] += v;
    }
 
    static long sum(long[] tr, int x) {
        long ans = 0;
        for (int i = x; i > 0; i -= lowbit(i)) ans += tr[i];
        return ans;
    }
 
    public static void main(String[] args) {
        Scanner f = new Scanner(System.in);
        PrintWriter w = new PrintWriter(System.out);
        List<int[]> tr = new ArrayList<>();
        int n = f.nextInt();
        for (int i = 1; i <= n; i++) {
            int l = f.nextInt();
            int r = f.nextInt();
            int c = f.nextInt();
            tr.add(new int[]{l, r, c});
        }
        Collections.sort(tr, (o1, o2) -> o1[0] == o2[0] ? o1[1] - o2[1] : o1[0] - o2[0]);
        long ans = 0;
        List<int[]> pre = new ArrayList<>();
        pre.add(new int[]{tr.get(0)[1], tr.get(0)[2]});
        for (int i = 1; i < n; i++) {
            int p_l = tr.get(i - 1)[0];
            int l1 = tr.get(i)[0], r1 = tr.get(i)[1], c1 = tr.get(i)[2];
            pre.add(new int[]{r1, c1});
            if (p_l == l1) {
            } else {
                for (int[] x : pre) {
                    int r = x[0], col = x[1];
                    if (col == 0) add(a, r, 1);
                    if (col == 1) add(b, r, 1);
                    if (col == 2) add(c, r, 1);
                }
                pre.clear();
            }
            if (c1 == 0) {
                ans += sum(b, N - 1) - sum(b, r1);
                ans %= mod;
                ans += sum(c, N - 1) - sum(c, r1);
                ans %= mod;
            }
            if (c1 == 1) {
                ans += sum(a, N - 1) - sum(a, r1);
                ans %= mod;
                ans += sum(c, N - 1) - sum(c, r1);
                ans %= mod;
            }
            if (c1 == 2) {
                ans += sum(a, N - 1) - sum(a, r1);
                ans %= mod;
                ans += sum(b, N - 1) - sum(b, r1);
                ans %= mod;
            }
        }
        w.println(ans);
        w.flush();
    }
}
0 回复 0 转发 0 喜欢 5 阅读
回复 (0)
默认 最新
暂无回复,快来抢沙发!