2020暑期D2-G 思路+证明
主为自用，欢迎指正。

https://ac.nowcoder.com/acm/contest/5667/G

前置知识：
sort(add1,add2,cmp)。

bitset定义以及其常用函数。

二分查找函数：
lower_bound(起始地址，结束地址，要查找的数值) 返回的是数值 第一个 出现的位置。（pos = lower_bound( number, number + 8, 111) - number， pos = 8，即number数组的下标为8的位置（但下标上限为7，所以返回最后一个元素的下一个元素）。）

upper_bound(起始地址，结束地址，要查找的数值) 返回的是数值 最后一个 出现的位置。

binary_search(起始地址，结束地址，要查找的数值) 返回的是是否存在这么一个数，是一个bool值。

题意：
A数组长度为n，B数组长度为m，m=min（m，4000）；若A中存在长度为m的连续子序列S，且S[i]>=B[i]。例，A={1，4，2，8，5，7}；B={3，2，3}；得S={4，2，8}、{8，5，7}（S数组与B数组同位置数字比较）；
求多少个满足条件的子序列S。

应该有很多种解法，这里我只写题解的方法，可能略有不同，把握住整体思路即可。

思路：
1.写出所有A[i]的关于B的bitset（任意B[j]，A[i]>=B[j]，则bitset=1，else bitset=0），若bitsetA[i+j-1][j]==1(j∈{1，2，...，m}).则A数组的子序列S=（A[i],A[i+1],...,A[i+m-1]）。
2.用这种思路找到实现方法后，首先我们需要得到bitset，其次实现bitsetA[i+j-1][j]==1(j∈{1，2，...，m})。
3.如何得到bitset呢，推荐不了解的同学先去学习一下STL中的bitset定义以及函数，这里根据题目简单讲一下核心，建立一个bitset首先确定位置，随后确定值。本题只有S[i]>=B[i]才置1；故我们先对原B数组排升序，对数据结构b按照b.x(值)排升序，得到所有满足条件的位置（核心1），后在位置上赋值1（核心2）。
在实现步骤3的过程中，我们发现经过排序后得到的所有bitset值实际上是所有能够满足条件的可能值，记为s[]。即,若存在S子序列满足条件，则其所有bitset值一定在s数组中；
G-1.JPG证明最多只有m中bitset能够S子序列中的值的bitset。
G-2.JPG解释为何要用升序找bitset。
理解了步骤1的同学得想到，S子序列的各个bitset值之间是存在着bitsetA[i+j-1][j]==1(j∈{1，2，...，m})的关系的，既然bitsetA[i+j-1]属于s数组，那么我们就不用再去求bitsetA啦；
直接在bt数组中找需要的bitset值，后把所有满足‘bitsetA[i+j-1][j]==1(j∈{1，2，...，m})’条件的S子序列找出来累加即可。
4.最后就是如何实现‘bitsetA[i+j-1][j]==1(j∈{1，2，...，m})’呢。首先我们需要确定A[i]是s数组中的哪一个bitset，也就是找到相应的位置，随后判断A[i]的bitset[j]是否等于1，如果成立则,i++&&j++，继续判断;但是这样将多了一个O（n）。
这时候让我们总结一下共识，若要存在一个S，则A[i]的bitset[j]==1,A[i+1]的bitset[j+1]==1，那么我们能否通过移位运算与与运算来代替遍历判断呢。即a=a&A[i]的bitset<<1,若a[j]==A[i]的bitset[j]==1；则a[j+1]==1,再运算a=a&A[i+1]的bitset<<1，则a[j+2]==1,就形成循环啦。
但是还有一个问题，如果中途中断了一次，那么循环就断了了，需要重新开始从ans[1]==1进行移位与与运算。但是我们又不想再写一个判断，所以再每次移位与与运算的时候再末尾都加一个1,即I=I.set(1);

代码步骤：
3.

sort(b+1, b + m+1, cmp);
    sort(B+1, B + m+1);
    for (int i = 1; i <= m; i++)
    {
        s[i] = s[i - 1];
        s[i].set(b[i].pos);
    }

4.

ans.reset();
    I.set(1);
    for (int i = 1; i <=n; i++)
    {
        pos = upper_bound(B+1,B+m+1, A[i]) - B - 1;
        ans = (((ans << 1) | I) & s[pos]);
        if (ans[m] == 1)
            cnt++;
    }

AC代码：

#define _CRT_SECURE_NO_WARNINGS
#include<cstdio>
#include<iostream>
#include<bitset> 
#include<vector>
#include<algorithm>
using namespace std;
bitset<40010>s[40010];
bitset<40010>ans, I;
struct node 
{
    int pos, x;
}b[40005];
int cmp(node a, node b)
{
    return a.x < b.x;
}
int A[200005], B[40005];

int main()
{
    int n, m;
    int cnt=0;
    int pos;
    scanf("%d %d", &n, &m);
    for (int i = 1; i <=n; i++)
    {
        scanf("%d", &A[i]);
    }
    for (int j = 1; j <=m; j++)
    {
        scanf("%d", &B[j]);
        b[j].pos = j;
        b[j].x = B[j];
    }
    sort(b+1, b + m+1, cmp);
    sort(B+1, B + m+1);
    for (int i = 1; i <= m; i++)
    {
        s[i] = s[i - 1];
        s[i].set(b[i].pos);
    }
    ans.reset();
    I.set(1);
    for (int i = 1; i <=n; i++)
    {
        pos = upper_bound(B+1,B+m+1, A[i]) - B - 1;
        ans = (((ans << 1) | I) & s[pos]);
        if (ans[m] == 1)
            cnt++;
    }
    cout << cnt << endl;
}

G-1.JPG
G-2.JPG