Description
给出一个长度为 $n$ 的数列 $\{a_i\}$ 和一个长度为 $m$ 的数列 $\{b_i\}$,求 $\{a_i\}$ 有多少个长度为 $m$ 的连续子数列能与 $\{b_i\}$ 匹配。
两个数列可以匹配,当且仅当存在一种方案,使两个数列中的数可以两两配对,两个数可以配对当且仅当它们的和不小于 $h$。
对于$100\%$的数据,$1\leq m\leq n \leq 150000$。
Solution
很明显,我们可以把检验配对的不等式变形:
$$a_i + b_i \ge h$$
$$a_i \ge h- b_i$$
令$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)$
Code
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 |
#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<<1|1].mn+=tr[x].tag; tr[x<<1|1].tag+=tr[x].tag; tr[x].tag=0; } inline void pup(int x){ tr[x].mn=min(tr[x<<1].mn,tr[x<<1|1].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<<1|1,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<<1|1,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); } |