问题分析

我们有 $n$ 个水平的货架（线段），第 $i$ 个货架在高度 $y = i$ 上，左右端点分别为 $(l_i, i)$ 和 $(r_i, i)$。

关键观察：当打开一个货架的水龙头时，水会从货架两端垂直流下，如果流经下方的其他货架，就会淹没那些货架。

更精确地说：对于货架 $i$，如果存在货架 $j$ 满足：

$j < i$（即货架 $j$ 在货架 $i$ 下方）

$l_j < \frac{l_i + r_i}{2} < r_j$（即货架 $i$ 的中点垂直投影落在货架 $j$ 上）

那么打开货架 $i$ 的水龙头也会淹没货架 $j$。

关键转化

设 $A_i$ 为指示随机变量，表示在随机排列中货架 $i$ 的水龙头被打开。

对于货架 $i$，$A_i = 1$ 当且仅当在排列中，所有能淹没货架 $i$ 的货架都在 $i$ 之后被考虑。

换句话说：设 $S_i$ 是能淹没货架 $i$ 的所有货架集合（即所有满足 $j > i$ 且货架 $j$ 的中点投影落在货架 $i$ 上的货架 $j$），那么货架 $i$ 被打开当且仅当在随机排列中，$i$ 出现在 $S_i$ 中所有元素之前。

算法实现

现在问题转化为：对于每个货架 $i$，计算有多少个货架 $j > i$ 满足 $l_i < \frac{l_j + r_j}{2} < r_i$。

高效计算方法

预处理：对于每个货架 $i$，计算其中点 $m_i = \frac{l_i + r_i}{2}$。

扫描线：按高度从高到低处理货架（即 $i$ 从 $n$ 到 $1$）：

对于当前货架 $i$，查询区间 $[l_i, r_i]$ 内有多少个中点

然后将 $m_i$ 加入数据结构

数据结构：使用树状数组或线段树来维护中点位置的计数。

时间复杂度：$O(n \log n)$