题目链接:https://loj.ac/problem/6062
留坑有空写
代码:
#include<bits/stdc++.h> using namespace std; const int MAXN=2e5+5; int a[MAXN],b[MAXN]; int n,m,h; struct seg { #define lson l,mid,rt<<1 #define rson mid+1,r,rt<<1|1 int mi[MAXN<<2],lazy[MAXN<<2]; inline void push_up(int rt) { mi[rt]=min(mi[rt<<1],mi[rt<<1|1]); } inline void push_down(int rt) { if(lazy[rt]) { mi[rt<<1]+=lazy[rt]; mi[rt<<1|1]+=lazy[rt]; lazy[rt<<1]+=lazy[rt]; lazy[rt<<1|1]+=lazy[rt]; lazy[rt]=0; } } void build(int l,int r,int rt) { lazy[rt]=0; if(l==r) { mi[rt]=-(m-l+1); // printf("%d\n",mi[rt]); return; } int mid=(l+r)>>1; build(lson); build(rson); push_up(rt); } void update(int L,int R,int val,int l,int r,int rt) { if(L>R) return ; if(L<=l&&r<=R) { lazy[rt]+=val; mi[rt]+=val; return ; } push_down(rt); int mid=(l+r)>>1; if(L<=mid) update(L,R,val,lson); if(mid<R) update(L,R,val,rson); push_up(rt); } }se; int getid(int x) { int p=upper_bound(b+1,b+1+m,x)-b-1; return p; } int pos[MAXN]; void solve() { for(int i=1;i<=m;i++) { scanf("%d",&b[i]); b[i]=h-b[i]; } se.build(1,m,1); sort(b+1,b+1+m); for(int i=1;i<=n;i++) { scanf("%d",&a[i]); a[i]=getid(a[i]); //printf("a[%d]->%d\n",i,a[i]); } int r=1; for(int i=1;i<=n;i++) { while(r<=n&&se.mi[1]<0) se.update(1,a[r++],1,1,m,1); pos[i]=(se.mi[1]>=0)?r-1:-1; se.update(1,a[i],-1,1,m,1); } int ans=0; for(int i=1;i<=n;i++) { if(pos[i]-i+1==m) ans++; } printf("%d\n",ans); } int main() { //freopen("in.txt","r",stdin); //freopen("out.txt","w",stdout); while(~scanf("%d%d%d",&n,&m,&h)) { solve(); } return 0; }