#5436. 「OOI 2016 Day 2」蝙蝠侠归来 题解

问题分析

我们需要在区间 $[l_i, r_i]$ 中找到一对下标 $(p, q)$，满足：

• $l_i \leq p < q \leq r_i$
• $h_p < h_q$
• 最大化 $q - p$

如果没有满足条件的对，输出 -1 -1。

关键观察

1. 问题转化

这是一个区间最大跨度对查询问题，但带有高度约束 $h_p < h_q$。

2. 候选对的性质

对于最优解 $(p, q)$：

• $h_p$ 应该是 $[l_i, q)$ 中小于 $h_q$ 且最左边的元素
• $h_q$ 应该是 $(p, r_i]$ 中大于 $h_p$ 且最右边的元素

3. 分治思路

考虑分治解决：对于区间 $[L, R]$，最优解要么完全在左半区间 $[L, mid]$，要么完全在右半区间 $[mid+1, R]$，要么跨越中点。

跨越中点的候选解：

• 对每个右半区的 $q$，在左半区找到满足 $h_p < h_q$ 且 $p$ 最小的位置
• 对每个左半区的 $p$，在右半区找到满足 $h_q > h_p$ 且 $q$ 最大的位置

算法框架

1. 分治预处理

使用分治算法预处理所有可能的候选对：

def solve(L, R):
    if L == R: return []
    mid = (L + R) // 2
    
    # 递归解决左右子问题
    left_pairs = solve(L, mid)
    right_pairs = solve(mid+1, R)
    
    # 处理跨越中点的候选对
    cross_pairs = []
    
    # 情况1：对每个右半区的q，找左半区最小的p满足h_p < h_q
    # 情况2：对每个左半区的p，找右半区最大的q满足h_q > h_p
    
    return merge(left_pairs, right_pairs, cross_pairs)

2. 候选对存储

对于每个区间 $[L, R]$，我们存储：

• 所有可能成为最优解的候选对 $(p, q)$
• 这些候选对按某种顺序组织以便快速查询

3. 查询处理

对于查询 $[l, r]$：

• 找到完全包含 $[l, r]$ 的线段树节点
• 在这些节点的候选对中寻找满足 $l \leq p < q \leq r$ 且 $q-p$ 最大的对

优化技巧

1. 单调性利用

在分治的跨越中点步骤中，可以使用单调栈来高效找到候选对：

• 从左往右扫描左半区，维护高度递减的单调栈
• 从右往左扫描右半区，维护高度递增的单调栈

2. 候选对剪枝

对于候选对 $(p, q)$，如果存在 $(p', q')$ 满足 $p' \geq p$ 且 $q' \leq q$ 且 $q'-p' \geq q-p$，那么 $(p, q)$ 可以被剪枝。

3. 线段树构建

将整个数组建立线段树，每个节点存储该区间内的所有候选对（经过剪枝的）。

复杂度分析

• 预处理：$O(n \log^2 n)$，分治过程中每个区间需要 $O(\text{len})$ 时间处理
• 存储空间：$O(n \log n)$，每个元素出现在 $O(\log n)$ 个区间中
• 单次查询：$O(\log^2 n)$，需要在 $O(\log n)$ 个节点中分别二分查找