算法思路

本题要求找到一个固定大小 $W \times H$ 的矩形，使其覆盖的垃圾总重量最大。这是一个二维区间最大和问题。

核心算法

1. 问题转换

将二维问题转换为一维问题：

• 由于矩形宽度固定为 $W$，我们可以用滑动窗口在 x 轴方向移动
• 对于每个 x 区间 $[x, x+W-1]$，我们需要找到在 y 轴方向高度为 $H$ 的区间能获得的最大重量和

2. 算法框架

使用扫描线 + 线段树的解法：

• 按 x 坐标排序所有点
• 用双指针维护 x 方向在 $[x_i, x_i+W-1]$ 范围内的点
• 用线段树维护 y 轴方向的高度区间和

3. 关键步骤

坐标离散化

sort(bx + 1, bx + n + 1), sort(by + 1, by + n + 1);
int lenx = unique(bx + 1, bx + n + 1) - bx - 1;
int leny = unique(by + 1, by + n + 1) - by - 1;

将 $10^9$ 范围的坐标映射到 $10^5$ 范围内，便于处理。

滑动窗口维护

for (int i = 1; i <= mxx; i++) {
    // 移除超出左边界的点
    for (int j = del + 1; j <= n; j++) {
        if (vx[i] - vx[t[j].x] + 1 > W) {
            // 从线段树中删除该点的影响
            modify(1, l, r, -t[j].w);
        } else {
            del = j - 1;
            break;
        }
    }
    
    // 添加当前x坐标的点
    for (int j : point[i]) {
        modify(1, l, r, t[j].w);
    }
    
    ans = max(ans, tree[1].mx);
}

线段树操作

线段树用于维护每个 y 坐标区间 $[y, y+H-1]$ 内的重量和：

• modify(): 区间加操作，添加或删除点的影响
• tree[1].mx: 根节点存储当前最大区间和

算法标签

• 扫描线算法 (Sweep Line)
• 线段树 (Segment Tree)
• 坐标离散化 (Coordinate Compression)
• 滑动窗口 (Sliding Window)
• 双指针技巧 (Two Pointers)

复杂度分析

• 时间复杂度: $O(N \log N)$
  • 排序和离散化: $O(N \log N)$
  • 线段树操作: 每个点最多被加入和删除一次，每次 $O(\log N)$
• 空间复杂度: $O(N)$

代码关键点解析

1. 离散化处理：

   int nowx = lower_bound(bx + 1, bx + lenx + 1, t[i].x) - bx;
   int nowy = lower_bound(by + 1, by + leny + 1, t[i].y) - by;
   

   将大范围坐标映射到小范围索引

2. y区间计算：

   int l = lower_bound(by + 1, by + leny + 1, vy[t[j].y] - H + 1) - by;
   int r = lower_bound(by + 1, by + leny + 1, vy[t[j].y]) - by;
   

   计算点 $y_j$ 影响的高度区间 $[y_j-H+1, y_j]$

3. 懒标记线段树：

   • 支持区间加操作
   • 支持区间最大值查询
   • 懒标记优化保证复杂度

样例验证

对于样例输入：

5 3 2
3 1 10
2 1 5
1 0 5
0 2 10
1 3 5

算法过程：

1. 按 x 排序点：x=0,1,1,2,3
2. 滑动窗口扫描：
   • 当窗口覆盖 x∈[1,3] 时
   • 包含点：(1,0,5), (2,1,5), (3,1,10)
   • 总重量 = 5+5+10 = 20（最大值）

该解法通过巧妙的坐标离散化和线段树维护，高效解决了二维区间最大和问题，能够处理 $10^5$ 规模的数据。