怎么全天下就我没见过？被薄纱了/ll
还是考虑从朴素的 DP 入手优化。不难发现对于固定的 \(i\)，相邻的 \(dp_{i,j}\) 的差要么是 \(0\) 要么是 \(1\)，也就是说从压位的考虑角度可能很有前途。因此我们转而维护 \(dp_{i,j}\) 的差分数组 \(v_{i,j}=dp_{i,j}-dp_{i,j-1}\)。考虑新添加一个元素 \(a_{i+1}\) 时候会发生什么变化：对于原来差分数组中每一段极长的连续段 \([l,r]\) 满足 \(v_{i,l}=v_{i,l+1}=\cdots=v_{i,r-1}=0,v_{i,r}=1\)，如果 \(b_l,b_{l+1},\cdots,b_{r-1}\) 中存在至少一个元素 \(=a_{i+1}\)，那么我们拎出最靠左的那个，假设为 \(b_j\)，那么变化是 \(v_{i+1,j}\) 变为 \(1\)，\(v_{i+1,r}\) 变为 \(0\)，否则这段的差分数组保持不变。
但是不好用 bitset 直接表示。考虑将其转化为可以用 bitset 直接维护的操作：
- 令 \(f\) 表示原来的差分数组，\(g\) 表示 \(f\) 向右平移一位的数组（即 \(g_{i+1}=f_i,g_1=1\)）
- 令 \(f'\) 为将所有匹配位置变为 \(1\) 后的数组，即对于所有 \(b_j=a_{i+1}\)，\(f'_j=1\)，其余 \(f'_j=f_j\)。
- 令 \(g'=f'-g\)，其中减法为二进制整数的减法，即将一个 01 数组看作一个大数，其中第 \(i\) 位上的值为该数 \(2^i\) 位上的值。
- 那么我们再令 \(f'\) 每一位上的值与上 \((f'_i\oplus g'_i)\)，就是新的差分数组。
手玩一下就会发现上述过程与 DP 部分所述过程等价。
手写 bitset 即可。时间复杂度 \(\dfrac{nm}{\omega}\)。
const int MAXN=70000;
const int B=MAXN/64+1;
int n,m,a[MAXN+5],b[MAXN+5];
u64 pos[MAXN+5][B+5],f[B+5],g[B+5],h[B+5];
int main(){
scanf("%d%d",&n,&m);
for(int i=1;i<=n;i++)scanf("%d",&a[i]);
for(int i=1;i<=m;i++)scanf("%d",&b[i]);
for(int i=1;i<=n;i++)pos[a[i]][i>>6]|=(1ull<<(i&63));
for(int i=1;i<=m;i++){
memset(g,0,sizeof(g));memset(h,0,sizeof(h));
for(int j=0;j<=B;j++)g[j]|=f[j]<<1,g[j+1]|=(f[j]>>63&1);
g[0]|=2;
for(int j=0;j<=B;j++)f[j]|=pos[b[i]][j];
u64 c=0;
for(int j=0;j<=B;j++){
h[j]=f[j]-g[j]-c;
c=(c&&(f[j]==0))||((u64)(f[j]-c)<g[j]);
}
for(int j=0;j<=B;j++)f[j]&=(f[j]^h[j]);
}
int sum=0;
for(int i=0;i<=B;i++)sum+=__builtin_popcountll(f[i]);
printf("%d\n",sum);
return 0;
}