题解：P16835 【MX-X29-T6】『FeOI-6』伊茶波树

hzy_____ · 2026-06-07 22:29:36 · 题解

首先考虑建树过程。

将当前序列中所有最大值位置找出来，可以将序列分成很多段。然后每一段递归进去建出一颗“伊茶波树”。然后对于最大值位置，建出一颗二叉树，再连接上每一段的“伊茶波树”建成整个序列的“伊茶波树”。

显然发现方案数是：每次找到的最大值位置数量的卡特兰数的乘积。

先考虑不带修的做法。

首先对于每个值 x，求出所有极长可以连到一起的区间。

• 这样的区间需要满足 a_l=a_r=x,\max\limits_{l\le i\le r}a_i=x 并且极长。

这样的区间有 O(n) 个。

然后对于一次查询 [L,R]，考虑拆贡献。下文中 C 表示卡特兰数，cntx_{l,r} 表示区间 [l,r] 中有多少个 x。

然后考虑带修。首先可以容易发现还是维护极大区间，均摊下来还是只有 O(n) 个区间。

具体来说就是每次操作只会增加，所以只会断掉一些区间，修改 O(1) 个区间。

然后考虑贡献怎么算。

• 第一种。直接加上时间维三维偏序即可，因为贡献是固定的。用树套树可以在线维护。
• 第二种。

我们求区间 [L,R] 仅保留所有非严格前缀最大值位置后的序列 c。

然后我们按照值可以将其划分成很多连续段。贡献就是每段长度的卡特兰数。可以直接用 单侧递归线段树 维护。

但是可以发现这样有一些问题。具体来说，我们没法满足 l<L 和 r\le R 的限制。

先看若 r> R。 首先这是最后一段。其次这是区间 [L,R] 的最大值。那么直接暴力修复即可。

接着是可能 l\ge L。这种情况我们发现是某一连续段的开头是一个极大区间的左端点。

那么我们就对每个极大区间的左端点进行标记，再使用 单侧递归线段树 特殊处理掉这些贡献即可。

具体来说，我们在线段树上维护这个区间保留非严格前缀最大值位置后：最小值，最大值，最小值连续段长度，最大值连续段长度，最小值是否存在被标记位置，最大值是否存在被标记位置，总贡献。（如果不想用这么多变量，可以比如说若最小值被标记就将长度设为 -1 这样）。

然后由于需要单侧递归所以还要维护出右儿子在合并到当前点上后的对应变量。

并且特判只有一种值的情况，不过这个都可以封装，所以还是不难写的。

• 第三种。和第二种一样。可以直接将序列反过来然后使用上一个同样的东西维护。
• 第四种。显然只有区间最大值所在的极大区间可能有贡献（剩下的显然贡献都是 1）。可以直接找到然后和上面“暴力修复”的部分一起判断情况。

然后这样就做完了。时间复杂度 O(n\log^2n)。