[牛客竞赛]Greater and Greater

题目链接：Greater and Greater

题干

第一行给定n和m分别为数组A和B的长度，之后两行分别输入A和B，且满足1$\le$≤n$\le$150000，1$150000，1\le$m$m\le$min{n,40000}，求A的长度为m的子串S的个数，其中$minn,40000，求A的长度为m的子串S的个数，其中\forall$i$i\in$[0,m-1]，有S[i]>=B[i].

思路

代码

#include <algorithm>
#include <bitset>
#include <cstdio>
using namespace std;
#define N 150000 + 5
#define M 40000 + 5

int n, m, ans, A[N], B[M], Ord[M];
bitset<M> cur, Bs[M];

int GetRank(int x) {
    int l = 0, r = m;
    while(l < r) {
        int mid = (l + r) >> 1;
        if(x < B[Ord[mid]])
            r = mid;
        else
            l = mid + 1;
    }
    return l;
}

int main() {
    scanf("%d%d", &n, &m);
    for(int i = 0; i < n; i++)
        scanf("%d", A + i);
    for(int i = 0; i < m; i++) {
        scanf("%d", B + i);
        Ord[i] = i;
    }
    sort(Ord, Ord + m, [](int u, int v) {//Ord储存B数组下标，以B数组中元素实际的大小对Ord进行排序
        return B[u] < B[v];				//省去了创建结构体
    });
    for(int i = 1; i <= m; i++) {//这里与题解中的一点不同是，这里先把M种类型的Si先全部放到Bs数组中，								  等到使用的时候，再根据GetRank(A[i])来取
        Bs[i] = Bs[i - 1];
        Bs[i].set(Ord[i - 1]);
    }
    for(int i = n - 1; i >= 0; i--) {
        cur >>= 1;
        cur &= Bs[GetRank(A[i])];//GetRank函数用于寻找A[i]在B数组中的位置，依此来给题解中说的cur[i]								赋值，只不过这里用的是单个cur滚动，因此每次都赋给cur。
        if(A[i] >= B[m - 1])//将cur视为滑动窗口的话，这一步就是接着往前滑了
            cur.set(m - 1);
        ans += cur[0];
    }
    printf("%d\n", ans);
    return 0;
}

说明

输入

5 3
1 3 7 5
2 6 4

输出

1

• 31行~33行

  Ord[3]={0,2,1}，因为B[0]<B[2]<B[1].

• 34行~37行

  Bs[3]={{0,0,0},{1,0,0},{1,0,1},{1,1,1}}，因为大于B[Ord[i]]的数也一定大于B[Ord[i-1]]

• 38行到44行

  开始的时候，因为cur为{0,0,0}，第一次经过40行后依然是{0,0,0}，经过if语句后由于5>4，cur[2]=1，cur变成{1,0,0}；

  第二轮，经过39行，cur变成{0,1,0}；经过40行，由于7对应的Bs为{1,1,1}，故，cur依然为{0,1,0}，此处可以看出第39和40行其实保证了$\forall$∀i$\in$∈[0,m-1]，S[i]>B[i]这一要求，因为每一个循环确定一位，第39行右移一位，只有每一位都满足条件，这个1才会一直存在，某一位不满足，都会因为第40行的’&'运算而使这个1变成0；第二次经过if语句，可以发现因为7>4，cur[2]再次被赋值为1，我们明白了，第41和42行的if语句就是用来开始判断{A[i-m+1],A[i-m+2]……,A[i]}这个子串是否满足要求的，如果A[i]>B[m-1]，意味着该子串的最后一位满足条件，可能满足条件，可以继续向前判断。

  之后的情况就不再具体分析了，相信聪明的你一定明白题解的意思了，尤其是这个方程：
  $cur_i=((cur_i>>1)|I_m)\&S_i$curi​=((curi​>>1)∣Im​)&Si​