JAVA代码

在同一行或同一列的格子做区间和并，双重循环遍历横竖交叉的部分减一格

复杂度应该是$O(n^2)$，因为在n/2行n/2列的时候有$(n/2)^2$次去重判断

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.Comparator;
import java.util.Scanner;

public class Main{
    public static class Node{
        int k,l,r;

        public Node(int k, int l, int r) {
            this.k = k;
            this.l = l;
            this.r = r;
        }
    }
    public static class MyComparator implements Comparator<Node>{
        @Override
        public int compare(Node o1, Node o2) {
            if(o1.k<o2.k) return -1;
            else if(o1.k>o2.k) return 1;
            else if(o1.l<o2.l) return -1;
            return 1;
        }

    }
    static long ans = 0;
    static ArrayList<Node> row = new ArrayList<>(); 
    static ArrayList<Node> col = new ArrayList<>(); 
    public static void main(String[] args) throws IOException {
        Scanner scanner = new Scanner(System.in);
        int n = scanner.nextInt();
        while(n-->0) {
            int x1 = scanner.nextInt();
            int y1 = scanner.nextInt();
            int x2 = scanner.nextInt();
            int y2 = scanner.nextInt();
            if(x1==x2) row.add(new Node(x1,Math.min(y1, y2),Math.max(y1, y2)));
            else col.add(new Node(y1,Math.min(x1, x2),Math.max(x1, x2)));
        }
        row.sort(new MyComparator());
        col.sort(new MyComparator());
        row = merge(row);
        col = merge(col);
        for(Node r : row) {
            for(Node c : col) {
                if(c.l<=r.k&&r.k<=c.r&&r.l<=c.k&&c.k<=r.r) {
                    ans--;
                }
            }
        }
        System.out.println(ans);
    }
    private static ArrayList<Node> merge(ArrayList<Node> list) {
        ArrayList<Node> res = new ArrayList<>();
        Node last = new Node(-0x7fffffff,-0x7fffffff,-0x7fffffff);
        for(Node node : list) {
            if(last.k==node.k) {
                if(last.r<node.l) {//不挨边
                    res.add(last);
                    ans+=last.r-last.l+1;
                    last = node;
                }else {//挨边
                    last.r = Math.max(last.r, node.r);
                }
            }else {//不在一列或行
                if(last.k!=-0x7fffffff) {//排除第一次
                    res.add(last);
                    ans+=last.r-last.l+1;
                }
                last = node;
            }
        }
        res.add(last);
        ans+=last.r-last.l+1;
        return res;
    }
}