问题分析

我们需要计算在任意时刻 $t \in (-\infty, +\infty)$ 和任意空间点 $(x,y)$ 上，最多能被多少片云同时覆盖。

云朵运动特性

• 横向移动云 ($d_i = 0$)：沿 $x$ 轴正方向匀速运动
• 纵向移动云 ($d_i = 1$)：沿 $y$ 轴正方向匀速运动

关键观察：最多只有2片云能同时覆盖同一个点，因为横向云只能与纵向云相交。

算法思路

核心思想：相对运动 + 扫描线

将问题转化为判断是否存在某个时刻，使得一片横向云和一片纵向云相交。

坐标变换

对于两片云（一片横向 $H$，一片纵向 $V$），它们在时刻 $t$ 相交的条件是：

• 横向云 $H$ 在时刻 $t$ 的位置：$[x_1 + t, x_2 + t] \times [y_1, y_2]$
• 纵向云 $V$ 在时刻 $t$ 的位置：$[x_1', x_2'] \times [y_1' + t, y_2' + t]$

相交条件转化为：

$$x_1 + t \leq x_2' \quad \text{且} \quad x_2 + t \geq x_1' \quad \text{且} \quad y_1 \leq y_2' + t \quad \text{且} \quad y_2 \geq y_1' + t $$

关键优化

代码通过巧妙的变量代换，将四维条件简化为二维问题：

定义：

• 对于横向云：sum12 = x + y + h, sum21 = x + y + w
• 对于纵向云：sum12 = x + y + h, sum21 = x + y + w

代码详解

1. 数据结构

struct node {
    int x1, y1, x2, y2;    // 矩形边界
    int sum12, sum21;       // 关键变量：用于简化判断条件
    int hash;               // 离散化后的值
};

2. 离散化处理

// 收集所有关键值
for (int i = 1, x, y, w, h, d; i <= n; i++) {
    cin >> x >> y >> w >> h >> d;
    if (d) {
        cloud1[++n1] = {x, y, x + w, y + h, x + y + h, x + y + w, 0};
        hash[++cnt] = x + y + h;
    } else {
        cloud0[++n0] = {x, y, x + w, y + h, x + y + h, x + y + w, 0};
        hash[++cnt] = x + y + w;
    }
}

// 排序去重
sort(hash + 1, hash + cnt + 1);
cnt = unique(hash + 1, hash + cnt + 1) - hash - 1;

3. 四种相交情况检查

代码通过四种不同的扫描方式检查横向云和纵向云是否可能相交：

情况1：正向扫描

for (int i = 1, j = 1; i <= n0; i++) {
    while (j <= n1 && cloud1[j].sum21 <= cloud0[i].sum12)
        fw.modify(cloud1[j].hash, + cloud1[j].x2 + cloud1[j].y2, cnt), j++;
    
    if (- cloud0[i].x1 - cloud0[i].y1 + fw.getsum(cloud0[i].hash) >= 1)
        ans = 1;
}

情况2-4：其他三种扫描方式

分别检查不同的相对位置关系，确保覆盖所有可能的相交情况。

4. 树状数组优化

使用树状数组维护最大值，支持快速查询和更新：

class fenwick {
private:
    int c[N + 10];
public:
    inline void modify(int i, int val, int n) {
        for (; i <= n; i += lowbit(i))
            c[i] = max(c[i], val);
    }
    inline int getsum(int i) {
        int sum = -inf;
        for (; i; i -= lowbit(i))
            sum = max(sum, c[i]);
        return sum;
    }
};

算法正确性

相交条件推导

通过代数变换，将时空相交问题转化为静态的区间比较问题。四种扫描方式分别对应：

1. 横向云在纵向云的左下方相交
2. 横向云在纵向云的右下方相交
3. 横向云在纵向云的左上方相交
4. 横向云在纵向云的右上方相交

完备性保证

• 四种扫描方式覆盖了所有可能的相对位置关系
• 离散化确保大范围坐标的可处理性
• 树状数组提供高效的范围查询

复杂度分析

• 离散化：$O(n \log n)$
• 排序：$O(n \log n)$
• 扫描过程：$O(n \log n)$（每个云最多被插入和查询一次）
• 总复杂度：$O(n \log n)$，适合 $n \leq 10^5$ 的数据规模

算法优势

1. 高效性：将动态问题转化为静态问题处理
2. 简洁性：通过巧妙的变量代换大幅简化问题
3. 完备性：四种扫描确保不遗漏任何相交情况
4. 实用性：能够处理大范围坐标值

总结

本题通过精妙的数学变换和数据结构应用，解决了移动矩形最大重叠数的计算问题。核心创新在于：

• 将时空相交条件转化为代数不等式
• 使用离散化和树状数组高效处理大范围数据
• 通过四种扫描方式确保判断的完备性

该解法在理论复杂度和实际效率之间取得了良好平衡，体现了计算几何与数据结构的美妙结合。