面积并 & 周长并复习笔记

stripe_python · 2026-03-02 22:31:31 · 算法·理论

为什么不叫扫描线复习笔记？因为笔者认为面积并 & 周长并只是扫描线的一种应用，不能说面积并 & 周长并就是扫描线算法。

本文代码中会使用一个离散化板子，代码为：

template <class T, const int N>
struct discrete_map {
    int tot, width; T d[N];
    discrete_map() : tot(0), width(-1) {}
    void clear() {tot = 0, width = -1, memset(d, 0, sizeof(d));}
    void add(const T& v) {d[++tot] = v;}
    void operator() () {sort(d + 1, d + tot + 1), width = unique(d + 1, d + tot + 1) - d - 1;}
    int operator[] (const T& v) const {return lower_bound(d + 1, d + width + 1, v) - d;}
    T value(int x) const {return d[x];}
};

面积并

P5490 【模板】扫描线 & 矩形面积并。

贺一个 OI-Wiki 的图：

用一条扫描线从下往上水平扫描，将各个颜色的小矩形面积相加。

我们发现矩形的高是容易处理的，需要维护矩形的水平宽。

采取如下策略：将矩形下边界标记为 1，上边界标记为 -1，当扫描到一个边界时，将其 x 轴上的投影区间增加这个标记。

将问题抽象出来，相当于一个数据结构题，支持的操作有：

• 区间加法。
• 全局查询权值 >0 的区间长度和。

用线段树来维护这些操作。

请注意，这里的线段树管理的是一个投影区间，而不是普通线段树的单点。将值域离散化后，为了保证正确性，我们需要让 [l,r] 代表投影区间 [l,r+1]。这一 trick 称为右端点偏移。

在线段树上的每个节点，我们维护：当前节点的权值、投影线段覆盖的实际长度。后一项具有可加性。

因为我们每次都是全局查询，所以区间加法并不需要处理标记问题，直接递归更新权值，然后自底向上 pushup 更新实际长度。

复杂度 O(n \log n)。细节上，注意数组开几倍的问题。

::::info[代码]

#define int long long
const int N = 1e5 + 5;
int n;
discrete_map<int, N << 1> mp;
struct line {int x1, x2, y, type;} a[N << 1];

#define ls (rt << 1)
#define rs (rt << 1 | 1)
int w[N << 3], val[N << 3];
void pushup(int rt, int l, int r) {
    if (w[rt] != 0) val[rt] = mp.value(r + 1) - mp.value(l);
    else if (l == r) val[rt] = 0;
    else val[rt] = val[ls] + val[rs];
}
void update(int tl, int tr, int c, int l = 1, int r = mp.width, int rt = 1) {
    if (tl <= l && r <= tr) return w[rt] += c, pushup(rt, l, r), void();
    int mid = (l + r) >> 1;
    if (tl <= mid) update(tl, tr, c, l, mid, ls);
    if (tr > mid) update(tl, tr, c, mid + 1, r, rs);
    pushup(rt, l, r);
}

void _main() {
    cin >> n;
    for (int i = 1, cnt = 0, x1, y1, x2, y2; i <= n; i++) {
        cin >> x1 >> y1 >> x2 >> y2;
        a[++cnt] = {x1, x2, y1, 1}, a[++cnt] = {x1, x2, y2, -1};
        mp.add(x1), mp.add(x2);
    }
    mp(), sort(a + 1, a + 2 * n + 1, [](const line& a, const line& b) -> bool {
        if (a.y == b.y) return a.type > b.type;
        return a.y < b.y; 
    });
    int res = 0;
    update(mp[a[1].x1], mp[a[1].x2] - 1, a[1].type);
    for (int i = 2; i <= 2 * n; i++) {
        res += (a[i].y - a[i - 1].y) * val[1];
        update(mp[a[i].x1], mp[a[i].x2] - 1, a[i].type);
    } cout << res;
}

::::

练习

P1856 [IOI 1998 / USACO5.5] 矩形周长 Picture

::::success[题解] 我们发现面积并扫描线的过程也可以求出周长。具体地，扫描线每次移动时，投影线段覆盖的实际长度产生的变化量即为周长的相对变化量。

为了得到答案，我们只需扫描两次，用水平扫描线求出横向，用竖直扫描线求出纵向周长。

仍然可以用线段树优化，复杂度 O(n \log n)。 ::::

::::info[代码]

const int N = 5005;
int n;
discrete_map<int, N << 1> mp, mp2;
struct line {int l, r, pos, type;} a[N << 1], b[N << 1];

#define ls (rt << 1)
#define rs (rt << 1 | 1)
int w[N << 3], val[N << 3];
void build(int l = 1, int r = mp.width, int rt = 1) {
    w[rt] = val[rt] = 0;
    if (l == r) return;
    int mid = (l + r) >> 1; build(l, mid, ls), build(mid + 1, r, rs);
}
void pushup(int rt, int l, int r) {
    if (w[rt] != 0) val[rt] = mp.value(r + 1) - mp.value(l);
    else if (l == r) val[rt] = 0;
    else val[rt] = val[ls] + val[rs];
}
void update(int tl, int tr, int c, int l = 1, int r = mp.width, int rt = 1) {
    if (tl <= l && r <= tr) return w[rt] += c, pushup(rt, l, r), void();
    int mid = (l + r) >> 1;
    if (tl <= mid) update(tl, tr, c, l, mid, ls);
    if (tr > mid) update(tl, tr, c, mid + 1, r, rs);
    pushup(rt, l, r);
}

void _main() {
    cin >> n;
    for (int i = 1, cnt = 0, x1, y1, x2, y2; i <= n; i++) {
        cin >> x1 >> y1 >> x2 >> y2;
        a[++cnt] = {x1, x2, y1, 1}, b[cnt] = {y1, y2, x1, 1};
        a[++cnt] = {x1, x2, y2, -1}, b[cnt] = {y1, y2, x2, -1};
        mp.add(x1), mp.add(x2), mp2.add(y1), mp2.add(y2);
    }
    int res = 0;
    auto solve = [&](line* a) -> void {
        build();
        stable_sort(a + 1, a + 2 * n + 1, [](const line& a, const line& b) -> bool {
            if (a.pos == b.pos) return a.type > b.type;
            return a.pos < b.pos; 
        });
        for (int i = 1, last = 0; i <= 2 * n; i++) {  
            update(mp[a[i].l], mp[a[i].r] - 1, a[i].type);
            res += abs(val[1] - last), last = val[1];
        }
    };
    mp(), solve(a);
    mp2(), swap(mp, mp2), solve(b);
    cout << res;
}

::::

P9478 [NOI2023] 方格染色

::::success[题解] 95pts 是显然的，把斜线拆成单点以后跑面积并板子即可。

如果只有斜线，面积并是容易的。因为我们可以将重合的斜线合并起来，剩余斜线两两平行，可以直接计算。

考虑加入横竖线，对着斜线容斥。注意到一条斜线最多与横竖线有一个交点，且这个交点可以 O(1) 算出。枚举斜线对应的横竖线，处理出所有重叠点。

答案即为扫描线计算出的横竖线面积并 + 斜线面积并 - 重叠点数目。记斜线有 k 条，复杂度 O(n \log n+kn)。 ::::

::::info[代码]

#define int long long
const int N = 1e5 + 5;
int n, m, q, cnt;
discrete_map<int, N << 1> mp;
struct line {int x1, x2, y, type;} a[N << 1];
vector<tuple<int, int, int>> H, V, D, D0;

#define ls (rt << 1)
#define rs (rt << 1 | 1)
int w[N << 3], val[N << 3];
void pushup(int rt, int l, int r) {
    if (w[rt] != 0) val[rt] = mp.value(r + 1) - mp.value(l);
    else if (l == r) val[rt] = 0;
    else val[rt] = val[ls] + val[rs];
}
void update(int tl, int tr, int c, int l = 1, int r = mp.width, int rt = 1) {
    if (tl <= l && r <= tr) return w[rt] += c, pushup(rt, l, r), void();
    int mid = (l + r) >> 1;
    if (tl <= mid) update(tl, tr, c, l, mid, ls);
    if (tr > mid) update(tl, tr, c, mid + 1, r, rs);
    pushup(rt, l, r);
}
int scan() {
    mp(), sort(a + 1, a + cnt + 1, [](const line& a, const line& b) -> bool {
        if (a.y == b.y) return a.type > b.type;
        return a.y < b.y; 
    });
    int res = 0;
    update(mp[a[1].x1], mp[a[1].x2] - 1, a[1].type);
    for (int i = 2; i <= cnt; i++) {
        res += (a[i].y - a[i - 1].y) * val[1];
        update(mp[a[i].x1], mp[a[i].x2] - 1, a[i].type);
    } return res;
}

void merge() {
    if (D.empty()) return;
    sort(D.begin(), D.end());
    D0.emplace_back(D[0]);
    for (int i = 1; i < (int)D.size(); i++) {
        auto [b, x1, x2] = D[i]; int& nx2 = get<2>(D0.back());
        if (b == get<0>(D0.back()) && x1 <= nx2) nx2 = max(x2, nx2);
        else D0.emplace_back(b, x1, x2);
    }
}
int slash() {
    vector<pair<int, int>> p;
    int res = 0;
    for (auto [b, x1, x2] : D0) {
        res += x2 - x1 + 1;
        for (auto [y, x3, x4] : H) {
            int x = y - b;
            if (x1 <= x && x <= x2 && x3 <= x && x <= x4) p.emplace_back(x, y); 
        }
        for (auto [x, y1, y2] : V) {
            int y = x + b;
            if (x1 <= x && x <= x2 && y1 <= y && y <= y2) p.emplace_back(x, y);
        }
    }
    sort(p.begin(), p.end()), p.erase(unique(p.begin(), p.end()), p.end());
    return res - (int)p.size();
}

void _main() {
    cin >> n >> n >> m >> q;
    for (int i = 1, opt, x1, y1, x2, y2; i <= q; i++) {
        cin >> opt >> x1 >> y1 >> x2 >> y2;
        if (opt == 1) {
            a[++cnt] = {x1, x2 + 1, y1, 1}, a[++cnt] = {x1, x2 + 1, y1 + 1, -1};
            mp.add(x1), mp.add(x2 + 1);
            H.emplace_back(y1, x1, x2);
        } else if (opt == 2) {
            a[++cnt] = {x1, x1 + 1, y1, 1}, a[++cnt] = {x1, x1 + 1, y2 + 1, -1};
            mp.add(x1), mp.add(x1 + 1);
            V.emplace_back(x1, y1, y2);
        } else {
            D.emplace_back(y1 - x1, x1, x2);
        }
    }
    merge(), cout << scan() + slash();
}

::::

P8734 [蓝桥杯 2020 国 A] 奇偶覆盖

::::success[题解] 魔改扫描线流程容易死掉，考虑魔改扫描线中的线段树。

仍然将问题抽象出来，我们要维护这样一个问题：

• 区间加法。
• 全局查询权值为奇的区间长度和。
• 全局查询权值为偶的区间长度和。

用线段树维护：当前节点的权值 w、投影线段覆盖奇数次的长度 l_1、投影线段覆盖偶数次的长度 l_2。借助 w 的信息，后两者具有可加性。

记区间长度为 l，我们有：

• 若 w=0，l_0,l_1 直接由左右儿子转移。
• 若 w 为奇，此时我们需要排除 0 的干扰。
  这里我们需要仔细分析原本的 l_1,l_2，以及通过左右儿子转移的量中 0 的贡献。这些讨论并不复杂，但过于繁杂，这里略去。
  结果为：l_2 由左右儿子转移，l_1 \gets l-l_2。
• 若 w 为偶，同理可得 l_1 由左右儿子转移，l_2 \gets l-l_1。

然后正常扫描线，复杂度 O(n \log n)。 ::::

::::info[代码]

#define int long long
const int N = 1e5 + 5;
int n;
discrete_map<int, N << 1> mp;
struct line {int x1, x2, y, type;} a[N << 1];

#define ls (rt << 1)
#define rs (rt << 1 | 1)
int w[N << 4], l1[N << 4], l2[N << 4];
void pushup(int rt, int l, int r) {
    int len = mp.value(r + 1) - mp.value(l);
    if (w[rt] == 0) l1[rt] = l1[ls] + l1[rs], l2[rt] = l2[ls] + l2[rs];
    else if (w[rt] & 1) l2[rt] = l1[ls] + l1[rs], l1[rt] = len - l2[rt];
    else l1[rt] = l1[ls] + l1[rs], l2[rt] = len - l1[rt];
}
void update(int tl, int tr, int c, int l = 1, int r = mp.width, int rt = 1) {
    if (tl <= l && r <= tr) return w[rt] += c, pushup(rt, l, r), void();
    int mid = (l + r) >> 1;
    if (tl <= mid) update(tl, tr, c, l, mid, ls);
    if (tr > mid) update(tl, tr, c, mid + 1, r, rs);
    pushup(rt, l, r);
}

void _main() {
    cin >> n;
    for (int i = 1, cnt = 0, x1, y1, x2, y2; i <= n; i++) {
        cin >> x1 >> y1 >> x2 >> y2;
        a[++cnt] = {x1, x2, y1, 1}, a[++cnt] = {x1, x2, y2, -1};
        mp.add(x1), mp.add(x2);
    }
    mp(), sort(a + 1, a + 2 * n + 1, [](const line& a, const line& b) -> bool {
        if (a.y == b.y) return a.type > b.type;
        return a.y < b.y; 
    });
    int r1 = 0, r2 = 0;
    update(mp[a[1].x1], mp[a[1].x2] - 1, a[1].type);
    for (int i = 2; i <= 2 * n; i++) {
        r1 += (a[i].y - a[i - 1].y) * l1[1], r2 += (a[i].y - a[i - 1].y) * l2[1];
        update(mp[a[i].x1], mp[a[i].x2] - 1, a[i].type);
    } cout << r1 << '\n' << r2;
} 

::::

P3997 [SHOI2013] 扇形面积并

::::success[题解] 首先，一段扇形的面积为 \dfrac{\pi r^2(a_1-a_2+1)}{2m} \times \dfrac{2m}{\pi}=(a_1-a_2+1)r^2。

将整个区域切成 2m 份，如图所示：

将这 2m 份看作一个序列，则问题转为这样一个数据结构问题：

• 插入 [l,r] 中的数字。
• 查询第 k 大的数字。

离线扫描线，则插入操作变为在 l 处插入，r+1 处删除，顺序遍历即可，需要一个支持插入删除 kth 的数据结构。复杂度 O(n \log n)。 ::::

::::info[代码]

const int N = 2e6 + 5;
int n, m, k;
vector<int> x[N];
spn_multiset<int> st;

void _main() {
    cin >> n >> m >> k;
    for (int i = 1, r, a, b; i <= n; i++) {
        cin >> r >> a >> b;
        if (a > b) x[0].emplace_back(r);
        x[a + m].emplace_back(r), x[b + m].emplace_back(-r);
    }
    long long res = 0;
    for (int i = 0; i < 2 * m; i++) {
        for (int j : x[i]) {
            if (j > 0) st.insert(j);
            else st.erase(-j);
        }
        int len = st.size();
        if (len >= k) res += 1LL * st[len - k] * st[len - k];
    } cout << res;
} 

::::