[USACO18FEB] Snow Boots G (离线+并查集)

题目大意：略

网上各种神仙做法，本蒟蒻只想了一个离线+并查集的做法

对所有靴子按最大能踩的深度从大到小排序，再把所有地砖按照积雪深度从大到小排序

一个小贪心思想，我们肯定是在连续不能踩的地砖之前的一个位置开始跳，如果这都不能跳过这一段连续的坏地砖，说明这个靴子肯定不能用

那么离线靴子以后，会发现不能踩的瓷砖是逐渐添加上去的，相当于求序列中最长连续坏点的长度

可以用并查集维护，一个点如果不能踩，就去merge它左右也不能踩的地砖，即积雪深度大于等于这块地砖

再用并查集维护一个size表示当前联通块大小，发现最大的size始终都是递增的，所以并不需要什么额外的数据结构去维护

 1 #include <cstdio>
 2 #include <cstring>
 3 #include <algorithm>
 4 #define N 100100
 5 using namespace std;
 6 
 7 int n,B;
 8 int f[N],fa[N],sz[N];
 9 struct node{int id,dep;}d[N];
10 struct Boot{int s,d,ans,id;}b[N];
11 int cmpnode1(node s1,node s2){return s1.dep>s2.dep;}
12 int cmp1(Boot s1,Boot s2){return s1.s>s2.s;}
13 int cmp2(Boot s1,Boot s2){return s1.id<s2.id;}
14 int find_fa(int x){
15     int y=x;
16     while(fa[y]!=y) y=fa[y];
17     while(fa[x]!=y){
18         int pre=fa[x];
19         fa[x]=y;
20         x=pre;
21     }return y;
22 }
23 
24 int main()
25 {
26     scanf("%d%d",&n,&B);
27     for(int i=1;i<=n;i++)
28         scanf("%d",&f[i]),d[i].dep=f[i],d[i].id=i,fa[i]=i,sz[i]=1;
29     for(int i=1;i<=B;i++)
30         scanf("%d%d",&b[i].s,&b[i].d),b[i].id=i;
31     sort(b+1,b+B+1,cmp1);
32     sort(d+1,d+n+1,cmpnode1);
33     int k=1,x,y,fx,fy,ma=0;
34     for(int i=1;i<=n;i++)
35     {
36         while(d[k].dep>b[i].s)
37         {
38             x=d[k].id,fx=find_fa(x),ma=max(ma,sz[fx]);
39             if(f[x-1]>=f[x]){
40                 y=x-1,fy=find_fa(y);
41                 if(fy!=fx) fa[fy]=fx,sz[fx]+=sz[fy],ma=max(ma,sz[fx]);
42             }
43             if(f[x+1]>=f[x]){
44                 y=x+1,fy=find_fa(y);
45                 if(fy!=fx) fa[fy]=fx,sz[fx]+=sz[fy],ma=max(ma,sz[fx]);
46             }k++;
47         }
48         if(ma>b[i].d-1) b[i].ans=0;
49         else b[i].ans=1;
50     }
51     sort(b+1,b+B+1,cmp2);
52     for(int i=1;i<=B;i++)
53         printf("%d
",b[i].ans);
54     return 0;
55 }