https://loj.ac/p/6564
题意：求两个字符串的最长公共子序列，串长、字符集 \(\le 7\times10^4\)。
分析
我们知道，求 LCS 的经典方法是 DP，状态已经是 \(O(n^2)\) 级别，而且无法省掉状态。但是，我们可以发现，对所有 \(i,j\) 都有 \(f_{i,j+1}-f_{i,j}\le 1\)，由此可以发现 \(f_i\) 的差分是 01 序列，考虑 bitset 优化，分析一下转移式子 \(f_{i,j}=\max(f_{i-1,j},f_{i,j-1},f_{i-1,j-1}+[s_i=t_j])\)，（从下面开始 \(f\) 代表着 DP 数组的差分）现在在 \(j\) 处出现了 \(i,j\) 之间的匹配，那么从 \(j\) 往后扫，只要扫不到 1，那么 \(f_{i,j}\) 最优一定取在 \(f_{i,j-1}\)，对于扫到的第一个 1 也是如此，但该 1 往后便不再如此。即使这里面出现了更多能匹配的位置，\(f_{i-1,j-1}+1\) 的取值也只是和 \(f_{i,j-1}\) 相等，所以没有影响。
总结一下，我们要做的操作是：将其划分为若干段 00...01 序列，对每一段序列，找到其中出现的最早的能匹配的位置，将该位置设为 1，然后将最后一个 1 设为 0。对于最后面的一段全 0 序列，也如此做，但没有将最后一个 1 设为 0 的环节。
考虑这玩意怎么用 bitset 优化。常规的那些操作显然没啥效果，设 \(g_i\) 表示字符 \(i\) 的取值下标，注意到如果我们将 \(f_{i-1}\) 与 \(g_{s_i}\) 或起来得到 \(h\)，那么对于每一段划分出来的序列，相当于取序列的 lowbit，而取 lowbit 有一个做法是 \((x\oplus (x-1))\& x\)，套用这个做法，我们想要对每一段序列都减 1。发现 \(f_{i-1}\) 有一个性质是每一段的最后一位都为 1，那么把这个 1 通过右移移到下一个序列中，第一个序列手动在开头创造一个 1，然后让 \(h\) 减掉这个东西就能顺利套用了。
时间复杂度 \(O(\frac{n^2}{\omega}\))。