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

文章来自  Icontofig 's Blog // 我们的征程是星辰大海!Away From OI,Come to ICPC(查看友链请点About Me)

题目大意

给出一个长为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(m2/W)的(W为bitset优化的效果)

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

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

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

curi = ((curi+1 >> 1) | Im) & sposi。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;
}


Sign in to leave a comment.
No Leanote account ? Sign up now.
0 comments
Title - Artist
0:00