2020牛客多校第二场(G题)Greater and Greater
程序员文章站
2022-04-02 19:02:14
...
Greater and Greater
------------------------------------------------------------------------
题目描述:给定大小为n的序列A和大小为m的序列B,计算A中所有大小为m的子区间S,满足
输入描述:
第一行:两个整数n,m(1≤n≤150000,1≤m≤min{n,40000}).
第二行:n个整数A1,A2…An(1≤Ai≤10^9)
第三行:m个整数B1,B2…Bm (1≤Bi≤10^9)
输出描述:
只有一行,表示答案。
样例输入:
6 3
1 4 2 8 5 7
2 3 3
样例输出:
2
------------------------------------------------------------------------
分析:
题解思路:
考虑bitset,对每个A求一个长为m的bitset Si,其中Si[j]=1当且仅当Ai≥Bj。注意到本质只有O(m)种不同的bitset,具体就是把m个数排完序之后,第i个bitset就在第i-1个bitset的基础上在第i大的数对应的位置多一个1,所以预处理这些bitset复杂度是O(m2/w)的。再设n个长为m的bitset,记为curi,其中 curi[j]=1当且仅当∀k∈[ j,m],Ai+k-j ≥Bk。可知有:curi= ((curi+1 >>1)|Im)& Si其中Im表示一个只有第m位为1的bitset。所以只要统计有多少个curi的curi[1]=1即可,这就是最后的答案。写代码的时候可以不用把每个curi都存起来,只弄一个cur然后不断滚动就可以了。
时间复杂度:O(nm/W)
比赛的时候还以为是魔改KMP,结果被出题人预判了我的预判…
------------------------------------------------------------------------
这是出题人给的题解:
#include<bits/stdc++.h>
using namespace std;
#define N 150005
#define M 40005
int n,m,ans,A[N],B[M],Ord[M];
bitset<M> cur,Bs[M];
int cmp(int x,int y)
{
return B[x]<B[y];
}
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,mcp);
for(int i=1;i<=m;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])];
if(A[i]>=B[m-1]) cur.set(m-1);
ans+=cur[0];
}
printf("%d\n",ans);
}
------------------------------------------------------------------------
以下是我自己写的
#include<bits/stdc++.h>
using namespace std;
const int MAXN=15e4+5;
bitset<MAXN> bt,ans;
int n,m,a[MAXN],b[MAXN],ad[MAXN],bd[MAXN];
int cmp1(int x,int y)
{
return a[x]>a[y];
}
int cmp2(int x,int y)
{
return b[x]>b[y];
}
int main()
{
scanf("%d%d",&n,&m);
for(int i=1;i<=n;i++)
{
scanf("%d",a+i);
ad[i]=i;
}
for(int i=1;i<=n-m+1;i++)
ans[i]=1;
for(int i=1;i<=m;i++)
{
scanf("%d",b+i);
bd[i]=i;
}
sort(ad+1,ad+n+1,cmp1);
sort(bd+1,bd+m+1,cmp2);
for(int i=1,j=1;i<=m;i++)
{
while(j<=n&&a[ad[j]]>=b[bd[i]])
{
bt[ad[j]]=1;
j++;
}
ans&=bt>>bd[i]-1;
}
printf("%d\n",ans.count());
}