NFLS 集训 8.24 G 题解

Description

给定一棵树 n n n,点带权,求有多少个非空区间 [ l , r ] [l,r] [l,r] 使得存在一种选定方案,使得这些点覆盖了 [ l , r ] [l,r] [l,r] 中的所有整数恰好一次且这些点形成了一个包含根的连通块。

原数据范围: 1 ≤ n ≤ 1 0 4 , 1 ≤ v i ≤ 100 1 \le n \le 10^4,1 \le v_i \le 100 1≤n≤104,1≤vi​≤100
加强版数据范围: 1 ≤ n ≤ 1 0 5 , 1 ≤ v i ≤ 1 0 4 1 \le n \le 10^5,1 \le v_i \le 10^4 1≤n≤105,1≤vi​≤104

Solution

算法一

考虑 dp \text{dp} dp。

令 f u , l , r f_{u,l,r} fu,l,r​ 表示,能否在以 u u u 为根的子树中,选出一棵包含 u u u 的连通块且覆盖了 [ l , r ] [l,r] [l,r] 中的全部整数恰好一次。若可以则 f u , l , r = 1 f_{u,l,r}=1 fu,l,r​=1,否则 f u , l , r = 0 f_{u,l,r}=0 fu,l,r​=0。

然而即使使用 bitset 优化 f f f,其空间依然是无法接受的,所以我们考虑对状态设计进行修改。

注意到, u u u 一定要选( u u u 作为不需考虑的边界),所以从 u u u 的各个子树中选出来的区间一定不能包含 a u a_u au​,并且最终整棵以 u u u 为根的子树中选出来的区间一定要包含 a u a_u au​。因此,我们可以将状态一分为二: 令 f u , l , 0 f_{u,l,0} fu,l,0​ 表示,能否覆盖到 [ l , a u − 1 ] [l,a_u-1] [l,au​−1] 中的所有数;令 f u , r , 1 f_{u,r,1} fu,r,1​ 表示,能否覆盖到 [ a u + 1 , r ] [a_u+1,r] [au​+1,r] 中的所有数。那么,真实的 f u , l , r f_{u,l,r} fu,l,r​ 就是 f u , l , 0 f_{u,l,0} fu,l,0​ 和 f u , r , 1 f_{u,r,1} fu,r,1​ 作按位与的结果。这也是本题最精髓的一步,我在考场上并没有想到这一步降维操作,现在是真的学到了

下面以计算 f u , l , 0 f_{u,l,0} fu,l,0​ 为例。枚举一个满足 a v < a u a_v<a_u av​<au​ 的点 v v v,若 v v v 往右最远能够扩展到的 x x x(形式化地说, x x x 为最大的满足 f v , x , 1 = 1 f_{v,x,1}=1 fv,x,1​=1 的 x x x)满足 u u u 往左最远能够扩展到的位置不超过 x + 1 x+1 x+1, 那么可以将 u u u 与 v v v 的状态合并到一起。具体来说,对于每个 f v , l , 0 = 1 f_{v,l,0}=1 fv,l,0​=1,其都可以让 f u , l , 0 = 1 f_{u,l,0}=1 fu,l,0​=1,于是我们枚举一个 l l l 并让 f u , l , 0 f_{u,l,0} fu,l,0​ 对 f v , l , 0 f_{v,l,0} fv,l,0​ 做按位或。

计算 f u , r , 1 f_{u,r,1} fu,r,1​ 的方法与其基本相同。

于是,我们愉快地得到了一个 O ( n V ) O(nV) O(nV) 的做法,其中 V V V 是所有 v i v_i vi​ 的最大值。可以通过原题。

算法二

考虑使用 bitset 优化这个 dp \text{dp} dp。

该如何用二进制快速维护呢?下为方便叙述,仅考虑 f u , l , 0 f_{u,l,0} fu,l,0​ 的计算; f u , r , 1 f_{u,r,1} fu,r,1​ 同理。

不难发现,我们所要维护的就是:

  • 判断是否同时存在一个 x x x 使得 f v , x , 1 = f u , x + 1 , 0 = 1 f_{v,x,1}=f_{u,x+1,0}=1 fv,x,1​=fu,x+1,0​=1
  • ∀ l \forall l ∀l 将 f u , l , 0 f_{u,l,0} fu,l,0​ 对 f v , l , 0 f_{v,l,0} fv,l,0​ 做按位或。

对于前者,将 f u , 0 f_{u,0} fu,0​ 对应的二进制数左移 1 1 1 位然后将其对 f v , 1 f_{v,1} fv,1​ 做按位与并判断其是否非 0 0 0 即可。对于后者,直接将 f u , 0 f_{u,0} fu,0​ 对 f v , 0 f_{v,0} fv,0​ 做按位或即可。

时间复杂度 O ( n V w ) O(\frac {nV} {w}) O(wnV​),OJ 的位长为 64 64 64,算出来大概是 1.6 × 1 0 7 1.6 \times 10^7 1.6×107 左右,可以通过。

Summary

本题重点在于,通过所有儿子 v v v 都不能覆盖到 a u a_u au​ 并且最终状态一定要覆盖到 a u a_u au​ 的性质,将原状态 f u , l , r f_{u,l,r} fu,l,r​ 一分为二,大大降低了空间复杂度,方便了进一步的 bitset 优化。

妙题!

上一篇:P3984 高兴的津津


下一篇:压缩css