题目分析

这是一个矩形计数问题。给定由多个矩形水平拼接而成的围栏，需要计算所有完全包含在围栏内部的轴对齐矩形的数量。

核心思路

1. 问题转化

将问题转化为：在由不同高度矩形组成的多边形中，统计所有可能的子矩形数量。每个子矩形必须完全包含在围栏内部。

2. 关键观察

• 围栏可以看作高度序列 $h_1, h_2, \ldots, h_n$ 和宽度序列 $w_1, w_2, \ldots, w_n$
• 任何子矩形都由其底边位置、高度和宽度决定
• 子矩形的高度受限于其覆盖区间内的最小高度

算法框架

第一阶段：预处理排序

1. 按高度排序：将所有围栏段按高度从小到大排序，便于从低到高处理
2. 维护宽度信息：为每个围栏段记录原始位置和宽度

第二阶段：线段树维护

构建线段树来高效维护区间信息：

• 区间合并：处理相邻区间的合并情况
• 矩形计数：计算每个区间内能形成的矩形数量
• 边界处理：记录左右边界的延伸情况

第三阶段：分层处理

采用从低到高的分层策略：

1. 逐层添加：从最低的高度开始，逐步添加更高的围栏段
2. 动态更新：每次添加新高度时，更新受影响区间的矩形计数
3. 组合计算：利用组合数学公式计算不同高度层能形成的矩形数量

算法特点

数据结构设计

• 线段树：用于高效维护区间信息和快速更新
• 懒标记：标记完全覆盖的区间，优化合并操作
• 边界信息：记录每个区间的左右边界延伸情况

数学公式应用

使用组合数学公式计算矩形数量：

• 对于宽度为 $w$ 的区间，可形成的矩形数量为 $\frac{w(w+1)}{2}$
• 通过模运算处理大数情况

效率优化

• 离线处理：预先排序，避免重复计算
• 区间合并：减少不必要的递归操作
• 模运算优化：使用预计算的逆元加速除法运算

关键洞察

1. 高度单调性：按高度排序后，可以系统地处理所有可能的子矩形
2. 区间独立性：不同高度区间的矩形计数可以独立计算后组合
3. 边界传播：相邻区间的边界信息会影响矩形计数，需要特殊处理

总结

该算法通过巧妙的数据结构设计和分层处理策略，高效解决了大规模矩形计数问题。核心思想是将复杂的二维矩形计数转化为高度序列上的区间管理问题，利用线段树维护区间信息，结合组合数学公式快速计算矩形数量。这种方法在保证正确性的同时，实现了对 $N \leq 10^5$ 规模数据的高效处理。