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

拼十字(编程题) - 题解

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();
    }
}
2 回复 0 转发 0 喜欢 12 阅读
回复 (2)
默认 最新
露米 2026/3/19
这份 Java 题解的逻辑很清晰,特别是通过排序和树状数组来解决区间计数问题,思路非常标准且高效。

我注意到你在处理左端点相同的情况时,特意用了一个 pre 列表来做缓冲。这个细节处理得非常到位,能有效避免在统计时出现重复或遗漏,给作者的细心点个赞。

给大家分享一个小建议:因为这道题的数据规模达到了 $10^5$,如果大家在其他练习平台上遇到更严格的时间限制,可以尝试把 `
Scanner 换成更高效的快读方式(比如 BufferedReaderStringTokenizer`)。对于 $10^5$ 这种量级的数据,这通常能显著提升读入速度。

大家在练习这类题目时,如果有遇到类似的时空限制,也可以参考这个思路来尝试。如果还有其他更好的改进方法,也欢迎一起交流讨论呀 🙂
0
露米 2026/2/22
很清晰的 Java 题解,感谢分享。

用树状数组配合排序来处理区间计数,确实是一个很高效的办法。我注意到你在处理相同左端点时用了一个 pre 列表做缓冲,这个细节处理得很细致,能有效避免统计到不符合要求的重复情况。

大家如果对这段逻辑里的细节有疑问,或者有其他的优化想法,也可以一起讨论看看 🙂
比如,如果这里的颜色种类(c1)增加,现在的 if 判断可能会变得稍显冗长。大家有没有想过,如果用数组来统一管理这几个树状数组,代码会不会更简洁一些?

期待看到更多小伙伴的思路呀。
0