就是求 LCS，数据范围变成 \(70000\) 了。
还是考虑朴素的 DP 状态 \(f(i,j)=\max\{f(i-1,j),f(i,j-1),[a_i=b_j]f(i-1,j-1)\}\)。
一个可能有用的性质是 \(|f(i,j)-f(i,j-1)|\le1\)，如果能快速求出最后一行的差分就做完了。
这些差分都能表示成 \(01\) 串，看起来是很有前途的，把差分数组设为 \(d\)。
观察一下每次 \(i\) 加一时 \(d\) 的变化，先把所有 \(a_i=b_j\) 的 \(j\) 弄出来。
如果一个 \(j\) 大于 \(d\) 中 \(1\) 的最高位，且没有更大的 \(j’\) 了，显然能令 \(d_j=1\)。
考虑最低的 \(j\)，假设其低于 \(d\) 中最低的 \(1\)，那么让这个 \(1\) 移到 \(j\) 处是必然的。发现这个 \(j\) 也不可能造成其它贡献了。
实际上干的事是：有若干段 \(00\cdots01\)，后缀是 \(00\cdots0\)，每段的 \(1\) 尽量被 \(j\) 更新到前面（但不能到前一段），后缀 \(0\) 也把最小的 \(d_j\) 变成 \(0\)。
思考如何用位运算实现：
现在把数组 \(d\) 压成了数 \(D\)，\(a_i=b_j\) 的 \(j\) 压成了 \(X\)。
现在要把每一段最低的 \(1\) 给提出来。
如 \(11\cdots100\cdots0\)，要让最低的 \(1\) 和其它的区分出来，减 \(1\) 是一个很好的方法，所有 \(1\) 只有它变化了。
所有把变化了的抠出来，即异或，再与上原来的 \(1\) 即可。
具体式子是 \(D=((D|X)-(D<<1|1))\oplus(D|X)\&(D|X)\)。
代码：
#include <bits/stdc++.h>
using namespace std;
typedef unsigned long long ull;
const int N=70005,B=63,M=N/B+1;
int n,m,k,ans;
ull f[M],b[N][M];
int main(){
scanf("%d%d",&n,&m);
for(int i=0,x;i<n;i++) scanf("%d",&x),b[x][i/B]|=1llu<<i%B;
k=(n-1)/B+1;
for(int p;m--;){
scanf("%d",&p);
ull c=1;
for(int i=0;i<k;i++){
ull x=f[i],y=x|b[p][i];
x+=x+c+(~y&((1llu<<B)-1));
f[i]=x&y;c=x>>B;
}
}
for(int i=0;i<k;i++) ans+=__builtin_popcountll(f[i]);
printf("%d\n",ans);
return 0;
}
原文地址：http://www.cnblogs.com/shrshrshr/p/16830572.html
