做题记录 25.8.27

· · 个人记录

\textcolor{black}\odot P10145 [WC2024] 线段树

若线段树的结点 u 权值确定则 L_u,R_u 连边（L_u,R_u 为点 u 对应区间），则限制 (l,r) 满足当且仅当 l,r 在同一连通块中

每组限制赋随机权值，令 v_i 表示 i\to i+1 这条边被覆盖到的权值的异或和，则限制 (l,r) 相当于 v_{l\sim r-1} 都异或上该随机权值

考虑在给定的线段树上 dp

令 f_u 表示子树 u 中 L_u 和 R_u 连通的方案数，令 g_{u,i} 表示子树 u 中，L_u\sim i 都和 L_u 连通，i+1 不与 L_u 连通的方案数

若 R_u-L_u=1 则 f_u=g_{u,L_u}=1

答案显然为 f_u+\sum_i [v_i=0] g_{u,i}

设子树 u 的范围为 [l,r)，左右儿子为 ls,rs，分割点为 m，转移为

g_{u,p}\gets g_{ls,p}f_{rs}\;(l\le p<m)\\ g_{u,p}\gets f_{ls}g_{rs,p}\;(m\le p<r)\\ g_{u,lp}\gets g_{ls,lp}g_{rs,rp}\;(l\le lp<m\le rp<r,v_{lp}=v_{rp})\\ f_{u}\gets 2f_{ls}f_{rs}+\sum_p g_{u,p}\\

维护 g'_{u,k}=\sum [v_p=k]g_{u,p}，容易线段树合并做到 O(n\log n)

时间复杂度 O(n\log n+m)

代码

参考