「Paint by Rectangles」算法题解

题目分析

给定 $N$ 个矩形，坐标都是 $1 \dots 2N$ 的排列，矩形将平面分割成若干区域。无穷大区域染白色，相邻区域颜色交替。
$T=1$ 输出总区域数，$T=2$ 输出白色和黑色区域数。

---

核心思路

1. 问题转化

将矩形边界视为平面图的边，区域视为面，使用平面图欧拉公式：

$$V - E + F = C + 1$$

其中 $V$ 是顶点数，$E$ 是边数，$F$ 是面数，$C$ 是连通分量数。

2. 关键观察

• 矩形边界形成平面图，是二分图 ⇒ 可二染色
• 外部无限区域为白色，相邻区域颜色交替
• 需要分别计算每个连通分量的区域数及染色

---

算法实现详解

1. 数据结构设计

Tree2：线段树维护区间颜色段

struct Tree2 {
    int l[M], r[M];
    node s[M];  // 存储颜色段信息
    bool bz[M]; // 懒标记
    
    // 维护区间颜色段的数量和端点颜色
    struct node {
        int cl, cr, cnt;  // 左端颜色、右端颜色、颜色段数
        node operator + (const node &t)const; // 合并区间
    };
};

用于统计扫描线过程中颜色段的变化，从而计算区域数。

Tree1：线段树维护矩形覆盖关系

struct Tree1 {
    int l[M], r[M], id1[M], id2[M]; // 存储覆盖的矩形ID
    
    // 查询区间内与当前矩形不同的其他矩形
    int qry(ci k, ci L, ci R, ci id);
};

用于在扫描线过程中检测矩形相交关系，维护连通性。

BIT：树状数组维护奇偶性

struct BIT {
    bool s[N];  // 用于维护奇偶性
    void add(int x);  // 单点异或
    int qry(int x);   // 前缀异或和
};

用于确定每个连通分量的染色情况。

2. 算法流程

步骤1：连通分量划分

// 使用扫描线 + 线段树维护矩形覆盖关系
for (int h = 1; h <= n * 2; ++h) {
    ci i = idx[h];
    if (xr[i] == h) // 矩形右边界
        in[i] = 0, T1.cov(1, yl[i], 0), T1.cov(1, yr[i], 0);
    
    // 合并相交的矩形
    while (1) {
        int tmp = T1.qry(1, yl[i], yr[i], f[i]);
        if (tmp) merge(f[i], tmp);
        else break;
    }
    
    if (xl[i] == h) // 矩形左边界
        in[i] = 1, T1.cov(1, yl[i], f[i]), T1.cov(1, yr[i], f[i]);
}

步骤2：分别处理每个连通分量

void Solve(vector<int>vec) {
    // 对每个连通分量单独计算区域数和染色
    vector<int>pos;
    for (int x : vec)
        pos.push_back(xl[x]), pos.push_back(xr[x]),
        v[xl[x]].push_back(make_pair(yl[x], yr[x] - 1)),
        v[xr[x]].push_back(make_pair(yl[x], yr[x] - 1));
    
    // 使用扫描线统计颜色段变化
    for (int i : pos) {
        for (auto tmp : v[i]) {
            T2.modify(1, tmp.first, tmp.second);
            node gt = T2.qry(1, tmp.first, tmp.second);
            // 根据颜色段变化更新区域计数
            Ans[gt.cr] += (gt.cnt + 1 >> 1) - (gt.cl == gt.cr);
            Ans[gt.cr ^ 1] += (gt.cnt >> 1) - (gt.cl != gt.cr);
        }
    }
}

步骤3：确定染色方案

// 使用树状数组确定每个连通分量的基准颜色
for (int i = 1; i <= n * 2; ++i) {
    if (xr[idx[i]] == i)
        B.add(yl[idx[i]] + 1), B.add(yr[idx[i]]);
    
    for (auto tmp : V[i]) {
        if (!B.qry(tmp.y))
            ans[0] += tmp.ans0, ans[1] += tmp.ans1;
        else
            ans[1] += tmp.ans0, ans[0] += tmp.ans1;
    }
    
    if (xl[idx[i]] == i)
        B.add(yl[idx[i]] + 1), B.add(yr[idx[i]]);
}

---

复杂度分析

• 连通分量划分：$O(N \log N)$
• 单个连通分量处理：$O(K \log N)$，其中 $K$ 是分量大小
• 总复杂度：$O(N \log N)$

---

算法标签

主要算法：

• 扫描线
• 线段树
• 平面图欧拉公式
• 并查集

相关技术：

• 树状数组
• 连通分量
• 区间操作
• 离散化

---

代码亮点

1. 分层处理：先划分连通分量，再分别处理
2. 双线段树：
   • Tree1 维护矩形覆盖关系
   • Tree2 维护颜色段信息
3. 奇偶性判断：用树状数组确定基准颜色
4. 懒标记优化：线段树使用懒标记提高效率

---

总结

这道题通过扫描线 + 线段树高效处理矩形相交关系，利用平面图性质和欧拉公式计算区域数量，再通过奇偶性判断确定染色方案。算法结合了多种数据结构和图论知识，是典型的USACO Platinum级别题目。