对于某个靴子，如果0代表某个格能走，1代表不能走，那么只要连续的1的个数的最大值>=靴子的步长，那这个靴子就不能用。
那么只要对靴子和格子都按深度排个序，然后从大到小来扫一遍（靴子越来越浅，能走的格子就越来越少，也就是相当于在增加1的个数），现在只要能维护把0变成1后，连续的1个数的最大值就行了
用并查集就可以了（好像双向链表或者线段树也行？）。
1 #include<bits/stdc++.h> 2 #define ll long long 3 #define pa pair<int,int> 4 using namespace std; 5 const int maxn=100010; 6 7 ll rd(){ 8 ll x=0;char c=getchar(); 9 while(c<‘0‘||c>‘9‘) c=getchar(); 10 while(c>=‘0‘&&c<=‘9‘) x=x*10+c-‘0‘,c=getchar(); 11 return x; 12 } 13 14 int N,M; 15 int d[maxn],siz[maxn],fa[maxn],ma,p[maxn]; 16 pa s[maxn],f[maxn]; 17 bool ans[maxn]; 18 19 int getfa(int x){return x==fa[x]?x:fa[x]=getfa(fa[x]);} 20 21 inline void add(int x){p[x]=1; 22 int l=getfa(x-1),r=getfa(x+1);x=getfa(x); 23 if(p[x+1]) fa[r]=x,siz[x]+=siz[r]; 24 if(p[x-1]) fa[l]=x,siz[x]+=siz[l]; 25 ma=max(ma,siz[x]); 26 } 27 28 int main(){ 29 int i,j,k; 30 N=rd(),M=rd(); 31 for(i=1;i<=N;i++) f[i]=make_pair(rd(),i); 32 for(i=1;i<=M;i++) s[i]=make_pair(rd(),i),d[i]=rd(); 33 sort(f+1,f+N+1);sort(s+1,s+M+1); 34 for(i=1;i<=N;i++) fa[i]=i,siz[i]=1; 35 for(i=M,j=N;i;i--){ 36 for(;j&&f[j].first>s[i].first;j--){ 37 add(f[j].second); 38 }ans[s[i].second]=d[s[i].second]>ma; 39 }for(i=1;i<=M;i++) printf("%d\n",ans[i]); 40 }
原文：https://www.cnblogs.com/Ressed/p/9610422.html