题目描述

这题是完全照搬yxc大佬的代码的，只是想添加一些自己写这题的想法，首先是不同行和不同列的存储过程，首先用segment中的k标记是某一行或者某一列，在用l和r标记左端点和右端点，列的情况也是类似的。

第二点，就是排序，相同列或者行，左端点小的位于前面（此处意味着对右端点没有任何处理，所以后续有一个max(r,q[k].r）的操作，不同行或者列，小的排在前面。

第三点，就是区间合并，此处我把区间合并的代码摘出来了，如下

    int l = -2e9, r = l - 1;
    for(int k = i; k < j; k ++ )
        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(r, q[k].r);

为什么需要声明r = l - 1呢，因为我们求区间长度的公式是r - l + 1。

第四点就是上面提及的不仅需要处理(r < q[k].l)，还要处理max(r, q[k].r);。

第五点：
就是对于任意一行，有多少列与其相交，相交即–，否则不变。
至于复杂度，目前还没总结，下次看视频的时候再补上，（可能会有点久）

C++ 代码

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

typedef long long LL;

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());

    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 ++ )
            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(r, q[k].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)
                res -- ;

    cout << res << endl;

    return 0;
}