OI Problems   关于

总体思路

首先记 ci=h−aic_i=h-a_i，则 aia_i 与 bjb_j 能匹配等价于 ci≤bjc_i \leq b_j。考虑建图，aia_i 对应结点 1∼n1\sim n，bib_i 对应结点 n+1∼n+mn+1\sim n+m，若 aia_i 与 bjb_j 能匹配就将它们连边。

考虑将 bb 和 cc 都从小到大排序，那么此时问题转化为考虑 bib_i 与 cjc_j 的匹配。注意到 bb 和 cc 有序，所以 bb 连边的结点是 cc 的一个前缀。那么考虑转化这个问题：对于 bi+1b_{i+1} 连向结点 cjc_j，若 bib_i 也连向 cjc_j，就忽略这条边，而是从 bi+1b_{i+1} 向 bib_i 连一条边。容易发现此时整个图是一棵树。


做法

若一段数符合条件，那么其任意一段前缀的和都不能为负数，并且容易发现这两个条件是等价的。于是我们只需要维护这个值就可以了。

容易发现这样的做法不需要用到树上信息，所以我们没有任何必要建出这棵树。

考虑到可能存在不在树上的点，所以我们需要建立一个总根 00，这个总根引出的一些代码细节需要特别注意。

  代码
// 2023.07.20

#include<bits/stdc++.h>
using namespace std;

int n,m,h,a[150001],b[150001],lastby[150001];

struct Node{
    int value,id;
    bool operator<(Node tmp)const{
        return value<tmp.value;
    }
}c[150001];

namespace SegmentTree{
    int val[610001],lazy[610001];
    void pushup(int id){
        val[id]=min(val[id<<1],val[(id<<1)+1]);
    }
    void pushdown(int id){
        if(lazy[id]){
            lazy[id<<1]+=lazy[id];
            val[id<<1]+=lazy[id];
            lazy[(id<<1)+1]+=lazy[id];
            val[(id<<1)+1]+=lazy[id];
            lazy[id]=0;
        }
    }

    void build(int id,int l,int r){
        if(l==r){
            if(l)val[id]=m-l+1;
            return;
        }
        int mid=l+r>>1;
        build(id<<1,l,mid);
        build((id<<1)+1,mid+1,r);
        pushup(id);
    }

    void updateAdd(int id,int l,int r,int x,int y,int v){
        if(y==0)x=0; // 防止右端点为 0
        if(x<=l&&r<=y){
            lazy[id]+=v,val[id]+=v;
            return;
        }
        int mid=l+r>>1;
        pushdown(id);
        if(x<=mid)updateAdd(id<<1,l,mid,x,y,v);
        if(mid<y)updateAdd((id<<1)+1,mid+1,r,x,y,v);
        pushup(id);
    }

    int queryMin(int id,int l,int r,int x,int y){
        if(x<=l&&r<=y)return val[id];
        int mid=l+r>>1,res=0x7fffffff;
        pushdown(id);
        if(x<=mid)res=min(res,queryMin(id<<1,l,mid,x,y));
        if(mid<y)res=min(res,queryMin((id<<1)+1,mid+1,r,x,y));
        return res;
    }
}

int main(){
    scanf("%d%d%d",&n,&m,&h);
    for(int i=1;i<=m;i++)
        scanf("%d",b+i);
    for(int i=1;i<=n;i++)
        scanf("%d",a+i);
    sort(b+1,b+1+m);
    for(int i=1;i<=n;i++)
        c[i]={h-a[i],i};
    sort(c+1,c+1+n);
    if(b[1]<c[1].value)
        return printf("0\n"),0;

    int tmp=1;
    for(int i=1;i<=m;i++)
        while(tmp<=n&&c[tmp].value<=b[i])
            lastby[c[tmp++].id]=i;
    SegmentTree::build(1,0,m);
    for(int i=1;i<=m;i++)
        SegmentTree::updateAdd(1,0,m,1,lastby[i],-1);
    int answer=0;
    answer+=SegmentTree::queryMin(1,0,m,0,m)>=0;
    for(int i=m+1;i<=n;i++){
        SegmentTree::updateAdd(1,0,m,1,lastby[i-m],1);
        SegmentTree::updateAdd(1,0,m,1,lastby[i],-1);
        answer+=SegmentTree::queryMin(1,0,m,0,m)>=0;
    }
    printf("%d\n",answer);
    return 0;
}