令$f[i][j]$表示前i个数的后j位能否匹配b的前j位，有转移$f[i][j]=f[i-1][j-1] \ \&\  [b_{j}\le a_{i}]$

将$g[i][j]=[b_{j}\le a_{i}]$看成一个i为位数的二进制数，即$g[i]=\sum_{j=1}^{m}[b_{j}\le a_{i}]\cdot 2^{j}$，$f[i]$同理，那么就有$f[i]=f[i-1]\ \&\ g[i]$

考虑对于$g$预处理，由于这个值仅和最小的大于$a_{i}$的$b_{j}$有关，因此将b排序后求出每一个$b_{i}$所对应的g，在其中二分即可求出$a_{i}$所对应的g

但这样的空间复杂度打到了$o(\frac{m(2n+m)}{8})$，考虑将f滚动、求g的二分放到f转移时进行，空间降为$o(\frac{m^{2}}{8})$，可以通过

1 #include
2 using namespace std;
3 #define N 150005
4 struct ji{
5 int k,id;
6 bool operator < (const ji &a)const{ 7 return (ko,s,g[40005];
12 void write(bitset<40005> o){
13 for(int i=1;i<=m;i++){
14 int x=o[i];
15 printf("%d ",x);
16 }
17 printf("\n");
18 }
19 int main(){
20 scanf("%d%d",&n,&m);
21 for(int i=1;i<=n;i++)scanf("%d",&b[i]);
22 for(int i=1;i<=m;i++){
23 scanf("%d",&a[i].k);
24 a[i].id=i;
25 }
26 sort(a+1,a+m+1);
27 g[1][0]=1;
28 for(int i=1,j=1;i<=m;i=j){
29 while (a[i].k==a[j].k)j++;
30 g[j]=g[i];
31 for(int k=i;k<j;k++)g[j][a[k].id]=1;
32 }
33 o[0]=s[0]=1;
34 for(int i=1;i<=n;i++){
35 s=(((s<<1)|o)&g[upper_bound(a+1,a+m+1,ji{b[i],m+1})-a]);
36 if (s[m]==1)ans++;
37 }
38 printf("%d",ans);
39 }