这是Lowest JN dalao昨天上课讲的一道神题其实是水题啦
题意很简单，我们也很容易建模转化出一个奇怪的东西
首先我们对b进行sort，然后我们就可以通过二分来判断出这个数可以和哪些数配对
然后我们稍微想一下就可以知道：每一段区间都是b数组后缀的形式
证明很简单，如果假设当前的数与第\(i\)位上的\(b_i\)不匹配，那么对于比\(b_i\)更小的\(b_{i-1}\)肯定是无法匹配的
然后我们可以转化为一个类似于二分图的完美匹配的问题，只不过其中匹配的数如上面所言是后缀的形式
然后我们可以套一个叫霍尔定理的东西，证明自看
然后我们发现对于所有的\(b_i(1\le i\le m)\)，都需要有至少i根线段包含了它
更直接的，我们令一个统计数组\(c\)，开始时\(c_i\)都等于\(-i\)，这样每次只需要给一个后缀加1即可
然后查询是否可以实现只需要看一下最小值是否>=0即可
然后直接做是肯定T的，然后我们发现我们需要完成的任务：
- 区间加
- 区间减（在抵消之前的操作是会用到）
- 区间最值查询
这不就是线段树随便维护一下的东西吗。
CODE
#include<cstdio>
#include<algorithm>
using namespace std;
const int N=150005;
int a[N],b[N],c[N],r[N],n,m,ans,h;
struct segtree
{
int s,add;
}tree[N<<2];
inline char tc(void)
{
static char fl[100000],*A=fl,*B=fl;
return A==B&&(B=(A=fl)+fread(fl,1,100000,stdin),A==B)?EOF:*A++;
}
inline void read(int &x)
{
x=0; char ch=tc();
while (ch<'0'||ch>'9') ch=tc();
while (ch>='0'&&ch<='9') x=x*10+ch-'0',ch=tc();
}
inline int find(int x)
{
int l=1,r=m,res=m+1;
while (l<=r)
{
int mid=l+r>>1;
if (b[mid]>=x) res=mid,r=mid-1; else l=mid+1;
}
return res;
}
inline int min(int a,int b)
{
return a<b?a:b;
}
inline void up(int rt)
{
tree[rt].s=min(tree[rt<<1].s,tree[rt<<1|1].s);
}
inline void down(int rt)
{
if (tree[rt].add)
{
tree[rt<<1].add+=tree[rt].add; tree[rt<<1|1].add+=tree[rt].add;
tree[rt<<1].s+=tree[rt].add; tree[rt<<1|1].s+=tree[rt].add;
tree[rt].add=0;
}
}
inline void build(int rt,int l,int r)
{
if (l==r)
{
tree[rt].s=c[l];
return;
}
int mid=l+r>>1;
build(rt<<1,l,mid); build(rt<<1|1,mid+1,r);
up(rt);
}
inline void modify(int rt,int l,int r,int beg,int end,int k)
{
if (l>=beg&&r<=end)
{
tree[rt].add+=k; tree[rt].s+=k;
return;
}
int mid=l+r>>1;
down(rt);
if (beg<=mid) modify(rt<<1,l,mid,beg,end,k);
if (end>mid) modify(rt<<1|1,mid+1,r,beg,end,k);
up(rt);
}
inline int query(int rt,int l,int r,int beg,int end)
{
if (l>=beg&&r<=end) return tree[rt].s;
int mid=l+r>>1,res=1e9;
down(rt);
if (beg<=mid) res=min(res,query(rt<<1,l,mid,beg,end));
if (end>mid) res=min(res,query(rt<<1|1,mid+1,r,beg,end));
up(rt); return res;
}
int main()
{
//freopen("CODE.in","r",stdin); freopen("CODE.out","w",stdout);
register int i; read(n); read(m); read(h);
for (i=1;i<=m;++i)
read(b[i]),c[i]=-i; sort(b+1,b+m+1);
for (i=1;i<=n;++i)
read(a[i]);
build(1,1,m);
for (i=1;i<=m;++i)
{
r[i]=find(h-a[i]);
if (r[i]<=m) modify(1,1,m,r[i],m,1);
}
if (query(1,1,m,1,m)>=0) ++ans;
for (i=m+1;i<=n;++i)
{
r[i]=find(h-a[i]);
if (r[i-m]<=m) modify(1,1,m,r[i-m],m,-1);
if (r[i]<=m) modify(1,1,m,r[i],m,1);
if (query(1,1,m,1,m)>=0) ++ans;
}
printf("%d",ans);
return 0;
}