Nowcoder Muti-School Training 2 G Greater and Greater bitset加速

题目大意

给出一个长为n的数列A,一个长为m的数列B

求问A中有多少个长度为m的子区间S，满足S中的元素全都不小于B中下标对应的元素

题解

说实话真的还是对bitset的应用不熟悉。

这题bitset只是最后用来优化的。

首先我们假定一个tmp数组，其中tmp[i][j]表示对Ai是否≥Bj。

如果一个长度为m的子区间要成为满足题目条件的S，那么和tmp[i]数组有什么关系？

一定是要求：对于区间内每一个i及其对应位置的j，tmp[i][j]都为1.这是显然的。

考虑如何优化这个问题。

首先，大小关系其实本质上来说只有m+1种，也就是对于tmp[i]的取值最多有m+1种，所以我们可以将B数组内的数全部排序，然后用m+1个bitset（假设为s）逐位去置1，然后九不需要算tmp数组了，我们需要取用tmp的时候，只需要找到最后一个小于等于A[i]的B[j]（这里的B已经排序好了），然后取s[j]就可以了。而且bitset也会在我们接下来的做法中发挥很重要的作用。预处理这些bitset的复杂度是O(m²/W)的（W为bitset优化的效果）

之后考虑如何去搞这个题。

新设一个新的m位bitset，假设为cur_i，其中cur_i[j] = 1当且仅当对于所有的k∈[j，m]，A_i+k-j >= B_k，这样只需要求有多少cur_i[1] = 1即可。

首先可以确定A数组的后m-1个数是肯定不可以作为区间点的，毕竟区间长度都不够，所以我们可以按照下面的公式来做：

cur_i = ((cur_i+1 >> 1) | I_m) & s_posi。posi表示最后一个小于等于A[i]的B[posi]。

这样通过右移位来进行对齐,可以达到我们预期的效果。

而且，我们可以不用开n个cur，只需要开一个进行滚动就可以了。

最终的时间复杂度是O(nm/W)

代码

#include <bits/stdc++.h>
using namespace std;
typedef pair<int,int>PI;
const int maxn = 150005;
const int maxm = 40005;
PI a[maxn],b[maxm];
bitset<maxm>s[maxm];
bitset<maxm>cur,upd;
const int INF = 1e9+7;
int n,m;
int p;
int main(){
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cin >> n >> m;
    for(int i = 1;i <= n;++i){
        cin >> p;
        a[i].first = p;
        a[i].second = i;
    }
    for(int i = 1;i <= m;++i){
        cin >> p;
        b[i].first = p;
        b[i].second = i;
    }
    s[0].reset();
    b[m+1].first = INF;
    b[m+1].second = m+1;
    sort(b+1,b+m+2);
    for(int i = 1;i <= m;++i){
        s[i] = s[i-1];
        s[i].set(b[i].second);
    }
    int ans = 0;
    cur.reset();
    upd.reset();
    upd.set(m);
    for(int i = n;i > 0;--i){
        int pos = upper_bound(b+1,b+m+2,a[i]) - b - 1;
        cur = ((cur >> 1) | upd) & s[pos];
        if(cur[1]){
            ans++;
        }
    }
    cout << ans << endl;
    return 0;
}