算法1

（合并区间）

同行同列合并区间 并且计算染黑的总数（多于实际）
然后每行每列判断 是否相交，相交则–

时间复杂度

n2

C++ 代码

#include <iostream>
#include <algorithm>
#include <vector>

using namespace std;
typedef long long LL;
const int N = 10010;
struct Segment{
    int k;//行号或列号
    int l,r;//左右坐标
    bool operator < (const Segment& w)const{//重载 先按行/列，再按左右端点
        if(k != w.k) return k < w.k;
        if(l != w.l) return l < w.l;
        return r < w.r;
    }
};

LL merge(vector<Segment> &q)
{
    vector<Segment> w;//合并的临时对象
    sort(q.begin(),q.end());//nlogn
    LL res = 0;
    for(int i = 0; i < q.size();){//+
        int j = i;
        while(j < q.size() && q[j].k == q[i].k) j++;//相同行/列坐标范围
        int l = -2e9, r = l-1;
         for(int k = i; k < j;k++) {//+，++是On
            if (r < q[k].l) {
                res += r - l + 1;
                if (l != -2e9) w.push_back({q[i].k, l, r});
                l = q[k].l, r = q[k].r;
            } else r = max(q[k].r, r);
        }
        if(l != -2e9) w.push_back({q[i].k, l,r});//做后一组塞进去
        res += r - l + 1;
        i = j;
    }
    q = w;//拷贝回来 直接等于号就行
    return res;
}

int main()
{
    int n;
    cin >> n;
    vector<Segment> rows, cols;

    while (n--)
    {
        int x1, y1, x2, y2;
        cin >> x1 >> y1 >> x2 >> y2;
        if(x1 == x2) cols.push_back({x1,min(y1,y2), max(y1,y2)});
        else rows.push_back({y1, min(x1,x2), max(x1,x2)});
    }

    LL res = merge(rows) + merge(cols);
    for(auto r:rows)
        for(auto c:cols)
            if(r.k >= c.l && r.k <= c.r && c.k >= r.l && c.k <=r.r)//判断是否在范围内//n2
                res--;
    cout << res << endl;

    return 0;
}