Longest Common Subsequence

题意

求出长度为 $n$ 的数组 $A$ 和长度为 $m$ 的数组 $B$ 的最长不下降公共子序列的长度。

满足 $1\le n,m\le 10^6,1\le A_i,B_i\le 3$。

思路

因为 $1\le A_i,B_i\le 3$，所以答案应该时这个形式的 $1,1,\cdots,2,2,\cdots 3,3$。

考虑先先枚举 $1$ 和 $3$ 的个数再计算 $2$ 的个数，假设他们分别有 $i,j$ 个。

定义数组 $sumA_i=\sum\limits_{i=1}^n [A_i=2]$，$lA_i$ 为从左向右第 $i$ 个 $1$ 的位置，$rB_i$ 表示从右向左第 $i$ 个 $3$ 的位置，对于 $B$ 数组也同理。

因为其中 $1$ 和 $3$ 的区间不能重合（保证单调递增），所以需要满足 $lA_i<rB_j,lB_i<rB_j$。因为计算的时公共子序列，所以除去连个序列都拥有的 $1$ 和 $3$ 剩余的 $2$ 的数量应该取最小值。根据 $sum$ 的定义与前缀和的思想，有贡献的 $2$ 的数量为 $\min(sumA_{rA_j-1}-sumA_{lA_i},sumB_{rB_j-1}-sumB_{lB_i})$ 。

因为随 $i$ 增加 $j$ 的最大值会减小具有单调性，所以可以使用双指针来维护 $lA_i<rB_j,lB_i<rB_j$。

因为我们维护的时公共子序列，所以只有在满足 $sumA_{rA_j-1}-sumA_{lA_i}\le sumB_{rB_{j-1}}-sumB_{lB_i}$ 的情况下我们才可以取 $b$ 数组中间的贡献。

再进行移项得到 $sumA_{rA_j-1}-sumB_{rB_{j-1}}\le sumA_{lA_i}-sumB_{lB_i}$ 就可以使用树状数组维护了。

code