题目大意

给定一个长n的数列A和一个长m的数列B，要求计算有多少个A中长为m的子串C，每个C[i]分别>=B[i]。
以样例为例：
1 4 2 8 5 7
2 3 3
这里就有2,8,5和8,5,7符合条件。

解题思路

先附上出题人的写法严谨的题解，由于部分数学表述，所以可读性较差。（不应该自动打我的水印）

正片：

这题需要用到bitset数据结构进行优化，因为我们只需要在后面的dp中用到0或1两种状态，而且bitset可以进行各种二进制运算，节省时间复杂度。
先求出长为m的s[i]（s和ans均为bitset），s[i][j]表示了是否A[i]>=B[j]，所以不同的s[i]有m种。求出本质不同的那m种情况的bitset，在需要用F[i]时，就可以直接二分了。
在i满足A[i+j-1]>=B[j]时，会出现F[i][1]=1,F[i+1][2]=1,F[i+2][3]=1等等，因此设长度为m的ans，每次ans右移一位都与上A[i]。
此时ans[0]为F[i][1]&F[i+1][2]&F[i+2][3]……。若ans[0]的结果为1，则说明i可行。

AC代码（本人）

这种简化方法是我参考另外一位大佬完成，思路大致相同。 
#include<bits/stdc++.h>
using namespace std;
struct hh
{
	int x,y;
} a[150010],b[150010];
bitset<150010> t,ans;
int n,m,i,j=1;
bool cmp(hh x,hh y)
{
    return x.x>y.x;
}
int main()
{
    ans.set();
    scanf("%d%d",&n,&m);
    for(i=1;i<=n;i++)
	{
        scanf("%d",&a[i].x);
        a[i].y=i;
    }
    for(i=1;i<=m;i++)
	{ 
        scanf("%d",&b[i].x);
        b[i].y=i;
    }
    sort(a+1,a+n+1,cmp);
    sort(b+1,b+n+1,cmp);
    for(i=1;i<=m;i++)
	{
        while(j<=n && a[j].x>=b[i].x)
		{
            t.set(a[j].y);
            j++;
        }
        ans&=t>>(b[i].y-1);
    }
    printf("%d\n",ans.count());
    return 0;
}

正常写法

当然还有我队友按照这一套写的代码（转载自https://ac.nowcoder.com/acm/contest/view-submission?submissionId=44250008） 
#include<bits/stdc++.h>
using namespace std;
const int N=150010,M=40010;
bitset<M> a,b[N];
int n,m,ans,c[N],d[N],e[N];
int cmp(int x,int y){return d[x]<d[y];}
int main()
{
    scanf("%d%d",&n,&m);
    for(int i=0;i<n;i++) scanf("%d",&c[i]);
    for(int i=0;i<m;i++) scanf("%d",&d[i]),e[i]=i;
    sort(e,e+m,cmp);
    for(int i=1;i<=m;i++) b[i]=b[i-1],b[i].set(e[i-1]);
    for (int i=n-1;i>=0;i--)
    {
        a>>=1;int l=0,r=m;
        while(l<r)
        {
            int mid=l+r>>1;
            if(c[i]<d[e[mid]]) r=mid;
            else l=mid+1;
        }
        a&=b[l];
        if(c[i]>=d[m-1]) a.set(m-1);
        ans+=a[0];
    }
    cout<<ans<<endl;
    return 0;
}