欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页

2020牛客多校 2G.Greater and Greater(双指针+bitset优化)

程序员文章站 2022-04-02 19:03:14
...

题意:

给定长度为n的序列a,和长度为m的序列b
问有序列a中有多少个长度为m的连续子区间s,满足s(i)>=b(i)

数据范围:n<=150000,m<=min(n,4e3),1<=a(i),b(i)<=1e9

解法:

因为区间长度固定为m,所以可以只考虑统计有多少个位置可以作为区间的起点
反过来想,我们也可以统计有多少个位置不能作为区间的起点

做法:
1.对于b[1],计算出a中的哪些位置j满足a[j]<b[1],
这些a[j]不能作为s[1],将不合法位置的位置标记

2.对于b[2],计算出a中的哪些位置j满足a[j]<b[2],
这些a[j]不能作为s[2],那么这些位置的左边不能作为s[1],
将这些位置的左边一个位置标记(只标记起点)

3,在处理完b[m]之后,遍历[1,n-m+1],统计有多少个位置未被标记为不合法即可

优化:
1.因为我们不需要在意先处理b[i]还是先处理b[i+1],也就是可以随意决定处理顺序
那么我们可以对a[]和b[]排序,如果a[j]<b[i],b[i]<b[i+1],那么a[j]<b[i+1]也成立,是单调的
因此'计算出a中的哪些位置j满足a[j]<b[i]'这个过程可以用排序+双指针优化

2.因为需要'标记位置','计算每个位置左滑若干位置后的状态',标记和滑动操作可以用bitset来做

code:

#include<bits/stdc++.h>
using namespace std;
const int N=2e5+5;
const int M=4e4+5;
struct Node{
    int v,id;
    friend bool operator<(Node a,Node b){
        return a.v<b.v;
    }
}a[N],b[M];
bitset<N>ans;
bitset<N>temp;
int n,m;
signed main(){
    scanf("%d%d",&n,&m);
    for(int i=1;i<=n;i++)scanf("%d",&a[i].v),a[i].id=i;
    for(int i=1;i<=m;i++)scanf("%d",&b[i].v),b[i].id=i;
    sort(a+1,a+1+n);
    sort(b+1,b+1+m);
    int k=1;
    for(int i=1;i<=m;i++){
        while(k<=n&&a[k].v<b[i].v){
            temp[a[k].id]=1;//标记不合法位置
            k++;
        }
        ans|=(temp>>(b[i].id-1));
    }
    int cnt=0;
    for(int i=1;i+m-1<=n;i++){//i+m-1<=n
        if(!ans[i])cnt++;
    }
    printf("%d\n",cnt);
    return 0;
}