这数据Java是不是A不了?数组大了全是MLE,小了又是RE
查看原帖
这数据Java是不是A不了?数组大了全是MLE,小了又是RE
1004601
aaacccac楼主2023/5/22 21:16

import java.io.*;
import java.util.Arrays;
import java.util.HashSet;
import java.util.Iterator;

public class Main {

    static int n, N = (int) (1e6 + 10);
    static StreamTokenizer in = new StreamTokenizer(new BufferedReader(new InputStreamReader(System.in)));
    static int x1, y1, x2, y2;
    static int[] X = new int[N << 1];


    static class ScanLine implements Comparable<ScanLine> {
        int l, r, h;
        int mark;

        public ScanLine(int l, int r, int h, int mark) {
            this.l = l;
            this.r = r;
            this.h = h;
            this.mark = mark;
        }

        @Override
        public int compareTo(ScanLine o) {
            return this.h - o.h;
        }
    }

    static class SegTree {
        int l, r, sum; // sum表示被完全覆盖的次数
        int len; // 区间内被截的长度
    }

    static ScanLine[] scanLines = new ScanLine[N << 1];
    static SegTree[] segTrees = new SegTree[N << 2];

    public static void main(String[] args) throws IOException {

        in.nextToken();
        n = (int) in.nval;
        for (int i = 1; i <= n; i++) {
            in.nextToken();
            x1 = (int) in.nval;
            in.nextToken();
            y1 = (int) in.nval;
            in.nextToken();
            x2 = (int) in.nval;
            in.nextToken();
            y2 = (int) in.nval;
            X[2 * i - 1] = x1;
            X[2 * i] = x2;
            scanLines[2 * i - 1] = new ScanLine(x1, x2, y1, 1);
            scanLines[2 * i] = new ScanLine(x1, x2, y2, -1);
        }
        n <<= 1;
        Arrays.sort(scanLines, 1, n + 1);
        Arrays.sort(X, 1, 1 + n);
        int tot = unique(); // 去掉XX中重复的值,返回去重后的有效元素个数
        // init
        for (int i = 0; i < segTrees.length; i++) {
            segTrees[i] = new SegTree();
        }
        build_tree(1, 1, tot-1);
        int ans = 0;
        for (int i = 1; i < n; i++) {
            edit_tree(1, scanLines[i].l, scanLines[i].r, scanLines[i].mark);
            ans += (long)segTrees[1].len * (scanLines[i + 1].h - scanLines[i].h);
        }
        System.out.println(ans);
    }

    private static int unique() {
        int res;
        HashSet<Integer> set = new HashSet<>();
        for (int i = 1; i <= n; i++) {
            set.add(X[i]);
        }
        res = set.size();
        Iterator<Integer> iterator = set.iterator();
        int index = 1;
        while (iterator.hasNext()){
            X[index++] = iterator.next();
        }
        return res;
    }

    private static void edit_tree(int node, int L, int R, int mark) {
        int curL = segTrees[node].l;
        int curR = segTrees[node].r;
        if (X[curR + 1] <= L || R <= X[curL])
            return;
        if (L <= X[curL] && X[curR + 1] <= R) {
            segTrees[node].sum += mark;
            pushup(node);
            return;
        }
        int leftNode = node * 2;
        int rightNode = node * 2 + 1;
        edit_tree(leftNode, L, R, mark);
        edit_tree(rightNode, L, R, mark);
        pushup(node);
    }

    private static void pushup(int node) {
        int curL = segTrees[node].l;
        int curR = segTrees[node].r;
        if (segTrees[node].sum != 0)
            segTrees[node].len = X[curR + 1] - X[curL];
        else {
            int leftNode = node * 2;
            int rightNode = node * 2 + 1;
            segTrees[node].len = segTrees[leftNode].len + segTrees[rightNode].len;
        }
    }

    private static void build_tree(int node, int L, int R) {
        segTrees[node].l = L;
        segTrees[node].r = R;
        segTrees[node].len = 0;
        segTrees[node].sum = 0;
        if (L == R)
            return;
        int mid = (L + R) >> 1;
        int leftNode = node * 2;
        int rightNode = node * 2 + 1;
        build_tree(leftNode, L, mid);
        build_tree(rightNode, mid + 1, R);
    }
}

2023/5/22 21:16
加载中...