题目描述

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

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

把每一行每一列进行区间合并，算出区间和后，再去重

C++ 代码

#include<bits/stdc++.h>
using namespace std;
#define int long long
#define endl '\n'
#define inf 0x3f3f3f3f3f3f3f3f
int n;
typedef pair<int,pair<int,int>> pii;
vector<pii>row,col;
int merge(vector<pii>&segs){
    vector<pii>cnt;
    sort(segs.begin(),segs.end());
    int laast=-2e9,st=-2e9,ed=-2e9,sum=0;
    for(auto i:segs){
        if(i.first!=laast){
            if(laast!=-2e9) cnt.push_back({laast,{st,ed}});
            laast=i.first,st=i.second.first,ed=i.second.second;
        }else{
            if(ed<i.second.first){
                cnt.push_back({laast,{st,ed}});
                st=i.second.first,ed=i.second.second;
            }else ed=max(ed,i.second.second);
        }
    }
    if(laast!=-2e9) cnt.push_back({laast,{st,ed}});
    segs=cnt;
    for(auto i:cnt) sum+=i.second.second-i.second.first+1;
    return sum; 
}
signed main(){
    ios::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);

    cin>>n;
    while(n--){
        int x1,y1,x2,y2;
        cin>>x1>>y1>>x2>>y2;
        if(x1==x2) row.push_back({x1,{min(y1,y2),max(y1,y2)}});
        else if(y1==y2) col.push_back({y1,{min(x1,x2),max(x1,x2)}});
    }
    int res=merge(row)+merge(col);
    for(auto a:row){
        for(auto b:col){
            if(b.first>=a.second.first&&b.first<=a.second.second&&b.second.first<=a.first&&b.second.second>=a.first) res--;
        }
    }
    cout<<res;
    return 0;
}