格子染色

在二维平面上有一个无限的网格图形，初始状态下，所有的格子都是空白的。
现在有 n个操作，每个操作是选择一行或一列，并在这行或这列上选择两个端点网格，把以这两个网格为端点的区间内的所有网格染黑（包含这两个端点）。

问经过 n次操作以后，共有多少个格子被染黑，重复染色同一格子只计数一次。

输入格式
第一行包含一个正整数 n。
接下来n行，每行包含四个整数 x1,y1,x2,y2，表示一个操作的两端格子坐标。

若 x1=x2
则是在一列上染色，
若 y1=y2
则是在一行上染色。

保证每次操作是在一行或一列上染色。

输出格式
包含一个正整数，表示被染黑的格子的数量。

数据范围
1≤n≤10000
−1e9≤x1,y1,x2,y2≤1e9

样例

输入
3
1 2 3 2
2 5 2 3
1 4 3 4
输出
8

/*格子染色
* 透过现象看本质：区间合并
* 干扰：第一次拿到这道题，看到数据范围很大，但是数据量很少，于是想到离散化，但这一步其实可做也可不做，没必要做
* 是否需要离散化：如果要开一个很大的数组但是实际上用到的下标很少很少，此时可以离散化
* 但是对于本题的本质是区间和并(加去重)，所以没必要离散化
* 思路：
[1]对行和列分别区间和并，计算不重叠区间的个数res。区间和并的时间复杂度是O(nlogn)(主要耗费在排序)
[2]去重。遍历每一行和每一列，重叠的话将res减1。时间复杂度是O(r*(n-r))，r是指行的个数，当r=n/2=10000/2=5000是，复杂度最高为2.5e7
*/

#include<iostream>
#include<vector>
#include<algorithm>
using namespace std;

// 最后的结果可能爆int
typedef long long ll;

// 存储染色的区间端点
struct pos{
    int k;// 存储行号或者列号
    int l,r;//存储左右端点  
    // 重载比较函数
    bool operator<(const pos&p)const{
        if(k!=p.k) return k<p.k;
        if(l!=p.l) return l<p.l;
        return r<p.r;
    }
};

/*几个需要注意的点
* 区间和并之前一定要先排序，一定要先排序，一定要先排序
* 必须要记录下合并之后新的区间，然后复制给区间，或者作为结果返回
* 因为去重的时候，应该是行区间合并完之后，列区间合并完之后，进行去重
* 不更新的话，是对旧的区间进行去重，可能会多算
* 比如合并之前：
行2[1,3]和[2,5]
列2[1,4]
合并之前，重叠两次，实际上只重叠一次
*/
ll merge(vector<pos>&segs){
    vector<pos> te;
    // 区间和并先排序
    sort(segs.begin(),segs.end());
    ll ans = 0;
    for(int i=0;i<(int)segs.size();){
        int k=i;
        // 找到同一行的区间
        while(k<(int)segs.size()&&segs[k].k==segs[i].k) ++k;
        // 初始化区间端点
        int st=-2e9,en=st-1; // 将en设置成st-1，这样就不用判读当前区间是否合法
        // 合并同一行的区间
        for(int j=i;j<k;++j){
            if(en<segs[j].l) {
                ans += en-st+1;
                if(st!=-2e9) te.push_back({segs[i].k,st,en});
                st=segs[j].l,en=segs[j].r;
            }else{
                en = max(en,segs[j].r);
            }
        }
        ans +=en-st+1;
        if(st!=-2e9) te.push_back({segs[i].k,st,en});
        i=k;

    }
    segs=te;
    return ans;

}
int main(){
    int n;cin>>n;
    // 存储行区间
    vector<pos> rows;
    // 存储列区间
    vector<pos> cols;
    while(n--){
        int x1,y1,x2,y2;
        cin>>x1>>y1>>x2>>y2;
        if(x1==x2){
            //对列染色
            // 因为不知道y1,y2谁大谁小，用min，max得出较小的数、较大的数
            cols.push_back({x1,min(y1,y2),max(y1,y2)});
        }else if(y1==y2){
            //对行染色
            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) res--;
    cout<<res<<endl;
    return 0;
}