题意：水池中有 个石柱，高度分别为 。
水池的水位为 ，则第 个石柱的像的高度为 。
泉水精灵可以栖息在石柱或石柱的像上，并从左到右行走，高度必须单调递增。
询问有多少对
满足存在一种水位
使得泉水精灵可以从第
个石柱（或它的像）到达地
个石柱（或它的像）。
，时限 。
算法一：
枚举 组 ，再枚举 的
种选择，判断是否存在一种选择满足 。
复杂度 ，可以通过测试点 ，期望得分 。
算法二：
建立图论模型：对所有 ，在平面直角坐标系上标记点 和 ，共 个点。对于两个被标记的点 ，，若满足 且 ，则连接有向边
。本质上，我们想探究这张有向图的可达性。
点 是固定不动的，点
会随着 的变化而运动，相邻层之间的连边有 种可能的情况，每种情况生效的 都是一个区间。
于是，我们可以将
的可能取值划分为
个区间，每个区间内，有向图的结构都不变。
对于确定的图，简单
搜索（或递推）即可求出所有好对子，总复杂度 。
复杂度 ，可以通过测试点 ，期望得分 。
算法三：
沿用算法二的思路，对
分段讨论。
对于确定的图，按 坐标从左往右
DP，记 为在点 结束的路径出发点 坐标的最小值，转移显然。所有的 可以 求出。
记 ，，，则
都是好对子。
对每个 记录 的最小值，则好对子总数为 。
复杂度 ，可以通过测试点 ，期望得分 。
算法四：
记 ，存在符合题意的
当且仅当：存在 ，使得 严格递减， 严格递增。
之间是等号、不等号都可以。
形式化地，我们想要的是 。
让 从小到大增加， 之间的不等号会逐个改变，可以用
std::set 维护合法的极长“”区间。区间每次变化时（注意，可能有多个不等号同时变化），记下新的区间
，使用单调栈求出所有区间的下包络，容易求出子区间总数。
复杂度 ，期望得分
。
算法五：
延续算法四的思路， 可以转化为 中不存在 。
考虑水位变化给
带来的影响。我们只关心相邻的 的相对大小，不妨设 ，分类讨论可知
另一种情况类似。
对于每个 ，“不存在 ”都对 提出一个约束，形如“ 不属于某区间”。
现在问题就转化成，给出
个区间 ，求有多少对 满足 的并不是全集。
考虑用扫描线解决，枚举 ，我们要找到所有符合题意的 。
先离散化，每次
右移，新加入一个区间 ，将数组
的区间 赋值为 。这样，数组 中的最小值 就是最薄弱的位置， 时能覆盖全集， 时不能。
（或者用双指针解决）复杂度 ，期望得分 。
算法六：
延续算法五的思路，仍然求有多少对 满足 的并不是全集。
这些区间具有特殊性，通过复杂的讨论可以发现，
的并中至多有三个独立的区间，于是信息可以 储存与合并。
使用不可删双指针即可做到 。