CF1720D2 Xor-Subsequence (hard version) 笔记

考虑暴力，设 $f_i$ 表示考虑 $a_{[0,i]}$ 最长的美丽子序列：

$$f_i=\underset{j<i\wedge a_j\oplus i<a_i\oplus j}{max}{f}_j+1$$

一个前缀 $max$ 的 DP 形式，考虑优化，瓶颈在于条件不能转换为只含 $i/j$ 的比较。

$\oplus$ 启示 01 Trie，设 $a_{i,k}$ 表示 $a_i$ 的第 $k$ 位，那么 $a_j\oplus i<a_i\oplus j$ 等价于：

• $\mathrm{\forall }k\in (x,30],a_{j,k}\oplus i_k=a_{i,k}\oplus j_k$；
• $a_{j,x}\oplus i_x<a_{i,x}\oplus j_x$。

条件一可转换为 $a_{i,k}\oplus i_k=a_{j,k}\oplus j_k$。条件二说明 $a_{i,k}\oplus i_k\ne a_{j,k}\oplus j_k\wedge a_{j,x}\oplus i_x=0\wedge a_{i,x}\oplus j_x=1$，以上求 $max$ 每次在字典树上跑一遍 $a_i\oplus i$，每走一个节点查询一下另一个分支即可。具体实现上，插入的时候每个节点分别存 $i_x=0/1$ 的 $f_i$ 最大值，查询时用 $a_{i,x}$ 判断一下即可满足 $a_{i,x}\oplus j_x=1$。时空复杂度 $O(30n)$。