给出一个长度为 n 的数列 \{a_i\} 和一个长度为 m 的数列 \{b_i\},求 \{a_i\} 有多少个长度为 m 的连续子数列能与 \{b_i\} 匹配。
两个数列可以匹配,当且仅当存在一种方案,使两个数列中的数可以两两配对,两个数可以配对当且仅当它们的和不小于 h。
对于100\%的数据,1\leq m\leq n \leq 150000。
很明显,我们可以把检验配对的不等式变形:
令b_i’=h-b_i
要使其可完全匹配,那么应将选出的a_i和b_i’分别按照从大到小(或从小到大)排序,然后扫一遍,判断其是否满足这个等式即可。
但是如果这样的话复杂度就是O((N-M+1)\times M)(从长度为n中选长度为m的连续子数列有(n-m+1)种选法)
很明显,这个复杂度不够优秀。
那么我们可以用线段树来优化这道题。
令b_1’ \ge b_2’ \ge b_3’ \ge \dots \ge b_m’,则对于每个b_i’都应该有\ge i个a大于等于它。
所以,我们可以将a,b’离散化,对于每个b_i’,在线段树上的b_i’位置上减i,代表它需要i个数来大于等于它;对于每个a_i,在线段树上的[1,a_i]上加1,代表这些位置上的都比它小,为其产生贡献。
那么最后只要判断下线段树上是否每个点都是非负数即可。
注意,当两个b_i’相同时,只需要取i更大的即可,不能叠加。
那么,如何来判断线段树上是否每个点都是非负数呢?
只需要记录一个最小值,若最小值都大于等于0,那么肯定完全匹配。
所以,我们每次枚举一下区间,将[1,a_{i-m-1}]减去1,并将[1,a_i]加上1(移动区间),然后判断下最小值是否大于等于0即可。
复杂度非常优秀O((N-M+1)\times logN)
#include<bits/stdc++.h>
using namespace std;
inline int read(){
int res=0,f=1;char ch=getchar();
while(!isdigit(ch)) f=ch=='-'?-1:f,ch=getchar();
while(isdigit(ch)) res=(res<<3)+(res<<1)+(ch&15),ch=getchar();
return res*f;
}
int n,m,h,a[150010],b[150010],q[300010],tot,ans;
inline int cmp(int x,int y){return x>y;}
struct node{
int mn,tag;
}tr[300010<<2];
inline void psd(int x){
if(!tr[x].tag) return ;
tr[x<<1].mn+=tr[x].tag;
tr[x<<1].tag+=tr[x].tag;
tr[x<<11].mn+=tr[x].tag;
tr[x<<11].tag+=tr[x].tag;
tr[x].tag=0;
}
inline void pup(int x){
tr[x].mn=min(tr[x<<1].mn,tr[x<<11].mn);
}
inline void upd(int x,int l,int r,int L,int R,int v){
if(L<=l&&r<=R){
tr[x].mn+=v;
tr[x].tag+=v;
return ;
}
psd(x);
int mid=l+r>>1;
if(L<=mid) upd(x<<1,l,mid,L,R,v);
if(R>mid) upd(x<<11,mid+1,r,L,R,v);
pup(x);
}
inline void build(int x,int l,int r){
if(l==r){
tr[x].mn=0;
tr[x].tag=0;
return ;
}
int mid=l+r>>1;
build(x<<1,l,mid);
build(x<<11,mid+1,r);
}
inline int check(){
return tr[1].mn>=0;
}
int main(){
n=read(),m=read(),h=read();
for(int i=1;i<=m;i++) b[i]=read();
for(int i=1;i<=n;i++) a[i]=read();
for(int i=1;i<=m;i++) b[i]=h-b[i];
sort(b+1,b+m+1,cmp);
for(int i=1;i<=m;i++) q[i]=b[i];
for(int i=1;i<=n;i++) q[i+m]=a[i];
sort(q+1,q+m+n+1);
tot=unique(q+1,q+m+n+1)-q-1;
build(1,1,tot);
for(int i=1;i<=m;i++) b[i]=lower_bound(q+1,q+tot+1,b[i])-q;
for(int i=1;i<=n;i++) a[i]=lower_bound(q+1,q+tot+1,a[i])-q;
for(int i=1;i<=m;i++)
if(b[i]<h) upd(1,1,tot,b[i],b[i],b[i]==b[i-1]?-1:-i);
for(int i=1;i<=m;i++) upd(1,1,tot,1,a[i],1);
ans=check();
for(int i=m+1;i<=n;i++) upd(1,1,tot,1,a[i-m],-1),upd(1,1,tot,1,a[i],1),ans+=check();
printf("%d\n",ans);
}