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;
}