759. 格子染色 - AcWing题库

在二维平面上有一个无限的网格图形，初始状态下，所有的格子都是空白的。

现在有 $n$ 个操作，每个操作是选择一行或一列，并在这行或这列上选择两个端点网格，把以这两个网格为端点的区间内的所有网格染黑（包含这两个端点）。

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

输入格式
第一行包含一个正整数 $n$。

接下来 $n$ 行，每行包含四个整数 $x_1,y_1,x_2,y_2$，表示一个操作的两端格子坐标。

若 $x_1=x_2$ 则是在一列上染色，若 $y_1=y_2$ 则是在一行上染色。

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

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

数据范围
$1 \le n \le 10000$,
$-10^9 \le x_1,y_1,x_2,y_2 \le 10^9$

样例输入

3
1 2 3 2
2 5 2 3
1 4 3 4

输出

8

思路

题目中说每次都会有两个x 或者两个y 相等
当x相等的时候，两个坐标就在一条水平线上，所染色的格子就是$y_2-y_1+1$
反之，两个坐标就在同一列上，所有染色格子就是$x_2-x_1+1$
我们用两个数组分别存储染色每一列的情况和染色每一行的情况
也就是数组的每个值都需要存储三个数字
用colume来存储每行的数字，需要存储是第几行也就是x，后面两个值是存储这个数据的范围
row用来存储每一列，存储数字和colume一样

然后对两个数组分别进行排序和区间合并
每次合并完成就记录这个区间的个数，也就是染色了多少个地方
用cnt存储下来，这里注意cnt开成 long long
假设所有格子全部染色成功 那么就是 (-1e9~1e9)==2*1e9这么多个数
在就是n行 2*n*1e9 在加上列的 4*n*1e9，不知道算错没有，开longlong就对了

存下来后，然后看每行与每一列有没有交集，每一行与每一列肯定只有一个交集
如果有交集就得cnt--
怎么看有没有交集呢？
就是这一行的行数是不是在每一列的区间里面 && 每一列的列数是不是在这一行的区间里面

下面看代码

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

long long cnt; //存储所有染色格子的个数
typedef pair<int,int> PII;
vector<pair<int,PII>> colume,row; //colume存储某行需要染色,row存储某列需要染色
int n;

void merge(vector<pair<int,PII>>& t)
{
    vector<pair<int,PII>> res; //存储合并后的结果
    sort(t.begin(),t.end()); //排序

    int st=t[0].second.first; //直接开始维护第一个区间
    int ed=t[0].second.second;
    int item=t[0].first;

    for(int i=1;i<t.size();i++)
    {
        if(item==t[i].first)
        { //看是不是这一列或行
            if(ed<t[i].second.first)
            { //和这一列或行的下一段没有交集
                cnt=cnt+ed-(st-1); //没有交集了，存下上已经合并区间所有的数
                res.push_back({item,{st,ed}}); //把刚刚合并的区间放在res里面
                st=t[i].second.first; //更新到这一列或行的下一段区间
                ed=t[i].second.second;
            }
            else
            { //和下一段区间有交集
                if(ed<t[i].second.second) ed=t[i].second.second;
            }
        }
        else 
        { //开始下一列或行的区间
            cnt=cnt+ed-(st-1); //存下上一列或行的区间所有数
            res.push_back({item,{st,ed}}); //维护好的放在res中
            item=t[i].first; //更新到下一列或行
            st=t[i].second.first;
            ed=t[i].second.second;
        }
    }
    cnt=cnt+ed-(st-1); //最后一列或行的所有数
    res.push_back({item,{st,ed}});

    t=res; //将维护好的数组给原数组
}

int main()
{

    cin>>n;
    for(int i=0;i<n;i++)
    {
        int x1,y1,x2,y2;
        cin>>x1>>y1>>x2>>y2;
        if(x1==x2)colume.push_back({x1,{min(y1,y2),max(y1,y2)}});
        //如果x一样，就是把这一行染色
        else row.push_back({y1,{min(x1,x2),max(x1,x2)}});
        //否则就是把这一列染色
    }
    merge(row); //进行所有列的区间合并，并计算所有染色的格子数
    merge(colume); //进行所有行的区间合并，并计算所有染色的格子数

    for(auto a:row)
    {
        for(auto b:colume) //看一下有没有交集，有的话就得减掉交集
        {   //看看row列在不在colume这条的中间
            if(a.first>=b.second.first&&\
            a.first<=b.second.second&&\ 
            b.first>=a.second.first&&\ 
            b.first<=a.second.second) //还得同时colume在row这列中间
            cnt--;
        }
    }


    cout<<cnt<<endl;

    return 0;
}