洛谷P1884 [USACO12FEB] Overplanting S 题解

题目链接：P1884 [USACO12FEB] Overplanting S

题意：

扫描线板子，求矩形面积并：

给定 $n(n \le 10^5)$ 个矩形的左上角位置与右下角位置，求覆盖面积。

重叠部分只算一次，坐标范围 $-10^8 \le x_1,y_1,x_2,y_2 \le 10^8$ ，

这里介绍一种不用线段树的扫描线。

先把每个矩形还是拆成 $4$ 个点，并按每一维 $0/1$ 的分类方式确定每个点距离坐标轴左下角的位置

换句话说，我们将左上角的点当作 out ，左下角的点当作 in ，方便从下到上依次考虑每个点

考虑对点按 $x$ 顺序排序，对于相等的 $x$ ，我们把他们放到一个 multiset 里分类讨论 $y$ 的不同情况

因为用 multiset 排过序了，所以我们从下往上讨论每个 $y$ ，以类似于区间覆盖的方式计算它的总长度 $L$

这样它的贡献可以看作 $L\times (x_i - x_{\mathrm{last}})$ ，即以直线 $x=x_i$ 为底的一个个小矩形的总贡献。

其实我最先听说扫描线的时候就想到这个做法了，只是觉得自己大概没这个能力发现某种算法吧

不过没想到今天在刷其他 OIer 的博客时看到了这个解法，只能说，我应该更自信一点的。

时间复杂度 $\mathcal{O}(n \log n)$

代码：

#include <bits/stdc++.h>
using namespace std;
#define int long long
#define INF 0x3f3f3f3f3f3f3f3f
void up(int &x,int y) { x < y ? x = y : 0; }
void down(int &x,int y) { x > y ? x = y : 0; }
#define N ((int)(1e5 + 15))

struct node
{
    int x,y; char c1,c2;
}t[N * 4];
multiset< pair<int,char> > s;
int solve()
{
    int r = 0, last = -1, S = 0;
    for(auto i : s)
    {
        if(!S) { last = i.first; ++S; }
        else if(i.second) ++S; else --S;
        if(!S) { r += i.first - last; }
    }
    return r;
}
signed main()
{
    ios::sync_with_stdio(0);
    cin.tie(0);cout.tie(0);
    // freopen("check.in","r",stdin);
    // freopen("check.out","w",stdout);
    int n; cin >> n;
    for(int i = 1, a,b,c,d; i <= n; i++)
    {
        cin >> a >> b >> c >> d;
        a += 1e8; b += 1e8; c += 1e8; d += 1e8;
        t[4 * i - 3] = {a, b, 1, 0}; t[4 * i - 2] = {a, d, 1, 1};
        t[4 * i - 1] = {c, b, 0, 0}; t[4 * i] = {c, d, 0, 1};
    }
    sort(t + 1, t + 1 + 4 * n, [](node a, node b) { return a.x < b.x; });
    int last = 0, res = 0;
    for(int i = 1; i <= 4 * n; i++)
    {
        if(t[i].x != last) {
            if(!s.empty()) { res += (t[i].x - last) * solve(); }
            last = t[i].x;
        }
        if(t[i].c1 == 1) { s.insert({t[i].y, t[i].c2}); }
        else { s.erase(s.find({t[i].y, t[i].c2})); }
    }
    cout << res << '\n';
    return 0;
}

---

参考文献：

[1] https://www.luogu.com.cn/blog/pocafup/solution-p1884