P9152 Gauss(3500); 题解

· · 题解

首先，“i 能通过一趟列车在中途不停靠的情况下直达 j”（假设 i<j）这个限制等价于，\min(a_i,a_j)>\max_{k=i+1}^{j-1}a_k。区间 \max 启发我们在大根笛卡尔树上考虑这一限制。

首先这两个点一定存在祖先关系，否则它们的 \operatorname{lca} 就不满足限制。于是我们可以假设 i 在 j 子树中。若 i 在 j 的左子树中，那么其一定在 j 左儿子的右儿子链上（包括左儿子），因为若跳到了某个左儿子上，其父亲会不满足限制。i 在 j 右子树中的情况是对称的，那么上面的条件就变为 i 在 j 左儿子的右儿子链上，或者 j 右儿子的左儿子链上。

由于集合 S 合法的条件是按照高度排序后相邻城市合法，因此 S 排序后相邻点 a,b 一定满足 a 是 b 的祖先，且 b 在 a 左儿子的右儿子链上或是右儿子的左儿子链上。

先抛开区间的限制，考虑一次询问怎么做，我们可以考虑树形 dp，令 f_x 为以 x 开头的合法子集数量，g_{x,0/1} 表示 x 左儿子链/右儿子链的 f 值之和，转移很简单，答案就是所有权值在区间内的 x 的 f 值之和。

考虑原问题，我们使用扫描线，将询问挂在 l 上，并从大到小依次加入每个数并重新计算每个数的 f 值。由于较大的数不会影响较小的数的答案，[l,r] 的答案就是加入到 l 时所有 \leqslant r 的数的 f 值之和。

若数据随机，每个数在笛卡尔树上的期望深度很小，我们加入一个数只需将其 f 值设为 1 并更新其每个祖先的 dp 值，并使用树状数组维护 f 值来计算区间 f 值之和，时间复杂度为 O(n\log^2 n+q\log n)。

若数据不随机，我们不能暴力枚举每个祖先更新，有没有更好的办法呢？注意到转移形式很好，更新一个点的贡献不会被其他的点影响，我们可以考虑预处理一些点的转移对答案的贡献。

使用树上撒点分块，那么所有点与其关键祖先的距离不会超过根号。更新一个点时我们暴力向上更新这些祖先，并使用 O(1)-O(\sqrt n) 分块维护贡献，到了关键点后直接在这个关键点上加上这次更新的贡献系数。对于每个关键点，预处理其 f/g_0/g_1 加一对每个点 f 值造成的影响并做一个前缀和，询问时直接枚举关键点统计这个关键点上的贡献系数对答案的贡献就好了。

时间复杂度：O(n\sqrt n)，逐块处理空间是线性的。（假设 n,q 同阶）