高低位分治

· · 个人记录

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 问题考虑阈值分治。考察下述两个做法:

取阈值 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。代码。

:::::