正题
题目大意
给两个序列\(a,b\)求它们的最长公共子序列。
\(1\leq n,m,a_i,b_i\leq 7\times 10^4\)
解题思路
无意间看到的一个\(bitset\)科技。
首先设\(f_{i,j}\)表示\(a\)串匹配到第\(i\)个\(b\)串匹配到第\(j\)个时的最长长度，做过\(dp\)套\(dp\)的应该知道\(f_{i,j}\)的性质。
\[0\leq f_{i,j}-f_{i,j-1}\leq 1 \]基本的思路就是设\(01\)矩阵\(M\)满足\(f_{i,j}=\sum_{k=1}^jM_{i,k}\)然后用\(bitset\)优化转移
然后考虑一下怎么转移，我们先预处理出\(p\)数组其中\(p_i\)表示数字\(i\)出现的位置集合
我们的转移要把\(M\)中的\(1\)尽量的往前移动并且看能否加上一个新的\(1\)。
假设现在的字符是\(c\)，那么我们将使用\(p_c\)进行转移。
我们把\(M\)中每个\(1\)作为结尾分成若干段（最后的\(0\)也是一段，顺序是从低位到高位）。
那么对于一段中如果这一段\(p_c\)有\(1\)那么我们就取最前面的那个\(1\)，这样因为前面假设有\(j\)个\(1\)那么这次就匹配\(p_c\)最前面的那个作为\(j+1\)。
但是我们显然不可能一段一段做，我们可以考虑怎么把这个操作转成位运算