高低位分治
stripe_python
·
·
个人记录
P10408 「SMOI-R1」Apple
维护映射 f : 2^U \to \mathbb{N},其中 U=\{0,1,\cdots,n-1\}。进行 q 次操作:
- 给定 S,查询 \sum \limits_{T \subseteq S} f_T。
- 给定 S,x,令 f_S \gets x。
:::::success[题解]
动态 FMT 问题考虑阈值分治。考察下述两个做法:
- 修改单点改,询问枚举子集,复杂度 O(1) - O(2^n)。
- 修改求 FMT 增量,询问单点查,复杂度 O(2^n)-O(1)。
取阈值 k=\lfloor n/2 \rfloor,对低 k 位 FMT,高 k 位枚举子集。
具体地,将集合 S \subseteq U 表示为二元组 S=(S_0,S_1),其中 S_0=S \cap [0,k), S_1=S \cap [k,n)。维护
g_{S}=\sum_{T \subseteq S} [S_0=T_0] f_T
修改枚举 S_0' \supseteq S_0 更新 f_{(S_0',S_1)} \gets \delta,查询枚举 \sum \limits_{S_1' \subseteq S_1} f_{(S_0,S_1')} 即可。
复杂度平衡到 O(q 2^{n/2}) 可以通过。代码。
我们称本题的解法为高低位分治。
:::::
QOJ104 Longest beautiful sequence
给定 n 个集合 S_i 和序列 k_i。称子序列 i_1 \sim i_m 合法,当且仅当 \forall j \in [1,m), \left|S_{i_j} \cap S_{i_{j+1}}\right|=k_{i_j}。
求最长合法子序列,输出构造。
:::::success[题解]
不难列得平方 DP 转移
f_i=\max_{j<i} \left[|S_j \cap S_i|=k_i\right] (f_j+1)
记录决策点即可构造,复杂度 O(n^2) 无法通过。
高低位分治,取 S_0=S \cap [0,k),S_1 = S \cap [k,n),递推过程中维护
g_{S_0,S_1,k}=\max [T_0=S_0 \land |S_1 \cap T_1|=k] f_T
查询 f_i 时枚举 S_0,可列得 |S_0 \cap (S_i)_0|+|S_1\cap (S_i)_1|=k_i,直接查表 g_{S_0,(S_i)_1, k_i-|S_0\cap (S_i)_0|} 即可。
求出 f_i 后更新 g,枚举 S_1 对 g_{(S_i)_0, S_1, |S_1 \cap (S_i)_1|} 做 chkmax 即可。
复杂度 O(n2^{m/2}+m2^m),其中 m=20。代码。
:::::