题解

问题分析

题目要求模拟合并区间并计算每个区间积水容量的过程。积水容量的计算规则为：

• 对于区间 $[l, r]$ 中的每个位置 $p$，计算 $d_p = \min(\max(h_l..h_p), \max(h_p..h_r)) - h_p$
• 区间容量 $w = \sum_{p=l}^r d_p$

关键观察

1. 容量公式转换：

   $$w = \sum_{p=l}^r [\min(L_p, R_p) - h_p]$$

   其中 $L_p = \max(h_l..h_p)$，$R_p = \max(h_p..h_r)$

2. 简化计算：

   • 实际上 $\min(L_p, R_p)$ 就是整个区间 $[l, r]$ 的最大值
   • 因此 $w = (r-l+1) \times \max_{l \le i \le r} h_i - \sum_{i=l}^r h_i$

算法思路

并查集 + 线段树维护区间最大值和和：

1. 数据结构：

   • 使用红黑树 tree 维护当前所有区间
   • 两个线段树 sgtl 和 sgtr 分别维护从左到右和从右到左的"前缀最大值和"
   • ST 表快速查询区间最大值

2. 合并过程：

   • 每次合并相邻区间 $[lx, rx]$ 和 $[ly, ry]$
   • 更新线段树：将新区间的最大值传播到对应区间
   • 计算新区间容量并输出

核心函数说明

• 线段树操作：

  • upd()：区间取最大值操作（类似区间chkmax）
  • query()：查询区间和
  • 维护最小值、次小值等信息来优化区间取最大值操作

• 容量计算：

  sgtl.query(lx,ry) + sgtr.query(lx,ry) - len*qry(lx,ry) - sum[ry] + sum[lx-1]
  

  这里计算的是修正后的积水容量

算法步骤

1. 初始化线段树和ST表
2. 对于每个合并指令：
   • 找到要合并的两个区间
   • 更新线段树中的区间最大值信息
   • 计算新区间的积水容量
   • 输出结果

复杂度分析

• 预处理：$O(n \log n)$ 建ST表和线段树
• 每次合并：$O(\log n)$ 查找区间 + $O(\log n)$ 线段树操作
• 总复杂度：$O(n \log n)$

算法标签

• 线段树
• ST表
• 区间合并
• 红黑树/平衡树
• 数据结构维护
• 离线处理