CF793F Julia the snail

题意：有一个长为 的杆，上面有 条绳子，每条绳子可以让蜗牛从 爬到 （中途不能离开），保证 各不相同。蜗牛也可以自然下落。

现在有 次询问，询问 出发，途中高度不能低于 或高于 ，问最高能爬到的位置。

允许离线，，时限 。

---

考虑离线，将所有询问按照右端点排序，逐个处理。

在不断增大 时维护维护 为询问 的答案。

考虑所有终点在 的绳子 的影响。

对于某个 ，若 且 ，则可以将 改为 。

这可以用 状物来维护。

线段树上每个节点维护最大值和次大值，若只有最大值需要改变，则 修改，若不止最大值需要改变则递归下去。

这样，每次额外的递归都会合并两种不同的数，额外代价也就是 的。