笋

FireBladeMaster · 2024-02-06 19:47:38 · 题解

线段树等价于三角剖分。

可以转化为对于结点 [l,r) 你可以选择在 l,r 间连一条无向边或者不连。对于一个区间 [L,R)，如果 L,R 连通则我们知道他的区间和，否则不知道。

观察到一个线段树结点 [l,r) 下方的连边结构，应该是长这样的：

即：若当前左端点与右端点不联通，则与左端点联通的点全都在与右端点联通的点的左侧（或者说，存在一个 j 使得 l 所在连通块的所有点编号 \le j，r 所在连通块所有点编号 >j。

考虑如何进行这个 dp。记 f(o,j) 表示结点 o（其代表区间为 [l,r)）及其下方的连边，l 所在连通块编号最大值为 j 的方案数，g(o) 代表结点 o 及其下方连边使得 l,r 连通的合法方案数。

根据子结点选择 f,g，转移有四种：

1. 2g(lson)g(rson)\to g(o)
2. g(lson)f(rson,j)\to g(o),g(lson)f(rson,j)\to f(o,j)
3. g(rson)f(lson,j)\to g(o),g(rson)f(lson,j)\to f(o,j)
4. f(lson,j)f(rson,k)\to g(o),f(lson,j)f(rson,k)\to f(o,j)

第四类转移 f\times f 的转移需要注意：如上图，蓝色区域 [j+1,k] 中的点将会与 l,r 均不连通，我们需要保证这部分的点均不需要与外面的点联通。也就是说：这个蓝色区域满足每个需要确定的 [L,R) 均满足：L,R 都在里面，或者都不在里面。

考虑用一个异或哈希的方式维护，对每个 i 维护 q_i，每个询问的 L,R 赋随机权值 v，然后执行 q_L\operatorname{xor}v \to q_L,q_R\operatorname{xor}v \to q_R，并记录 q 的前缀异或为 V，则转移的条件是 V_j=V_k。

此时我们发现转移中我们可以把 j 改写为 V_j，这样转移变成了：

1. 2g(lson)g(rson)\to g(o)
2. g(lson)f(rson,j)\to g(o),g(lson)f(rson,j)\to f(o,j)
3. g(rson)f(lson,j)\to g(o),g(rson)f(lson,j)\to f(o,j)
4. f(lson,j)f(rson,j)\to g(o),f(lson,j)f(rson,j)\to f(o,j)

最后答案是 g(root)+f(root,0)。

上线段树合并，复杂度 O(n\log n)。