luogu4269 Snow Boots G (并查集)

提示：扫一扫查出行
【扫一扫了解最新限行尾号】
复制提示

对于某个靴子，如果0代表某个格能走，1代表不能走，那么只要连续的1的个数的最大值>=靴子的步长，那这个靴子就不能用。

那么只要对靴子和格子都按深度排个序，然后从大到小来扫一遍（靴子越来越浅，能走的格子就越来越少，也就是相当于在增加1的个数），现在只要能维护把0变成1后，连续的1个数的最大值就行了

用并查集就可以了（好像双向链表或者线段树也行？）。

 #include<bits/stdc++.h>

 #define ll long long

 #define pa pair<int,int>

 using namespace std;

 const int maxn=;

 ll rd(){

     ll x=;char c=getchar();

     while(c<''||c>'') c=getchar();

     while(c>=''&&c<='') x=x*+c-'',c=getchar();

     return x;

 }

 int N,M;

 int d[maxn],siz[maxn],fa[maxn],ma,p[maxn];

 pa s[maxn],f[maxn];

 bool ans[maxn];

 int getfa(int x){return x==fa[x]?x:fa[x]=getfa(fa[x]);}

 inline void add(int x){p[x]=;

     int l=getfa(x-),r=getfa(x+);x=getfa(x);

     if(p[x+]) fa[r]=x,siz[x]+=siz[r];

     if(p[x-]) fa[l]=x,siz[x]+=siz[l];

     ma=max(ma,siz[x]);

 }

 int main(){

     int i,j,k;

     N=rd(),M=rd();

     for(i=;i<=N;i++) f[i]=make_pair(rd(),i);

     for(i=;i<=M;i++) s[i]=make_pair(rd(),i),d[i]=rd();

     sort(f+,f+N+);sort(s+,s+M+);

     for(i=;i<=N;i++) fa[i]=i,siz[i]=;

     for(i=M,j=N;i;i--){

         for(;j&&f[j].first>s[i].first;j--){

             add(f[j].second);

         }ans[s[i].second]=d[s[i].second]>ma;

     }for(i=;i<=M;i++) printf("%d\n",ans[i]);

 }