题干信息解读

在一条由 N 块瓷砖组成的路径上，每块瓷砖 $i$ 覆盖着 $f_i$ 英尺的积雪。$John$ 有 $B$ 双靴子，每双靴子 $i$ 有最大承受积雪深度 $s_i$ 和最大步长 $d_i$。$John$ 必须从第 $1$ 块瓷砖出发，到达第 N 块瓷砖，且两块瓷砖无积雪。需要判断每双靴子是否能让 $John$ 完成这段旅程。

整体做题思路

1.离线处理：将靴子按最大承受积雪深度降序排序，同时记录原始索引。
2.维护可达性：使用并查集维护当前可到达的连续区间，初始时每个瓷砖自成一个集合。
3.处理瓷砖：按积雪深度降序处理每个瓷砖，将其加入并查集，并合并相邻的区间。
4.查询靴子：对于每双靴子，检查其最大步长是否能跨越当前所有不可达区间的最大长度。

难点和注意事项

1.离线处理：需将靴子按 s_i 排序，以便逐步处理积雪深度的限制。
2.并查集维护：合并区间时需动态更新区间长度，确保高效查询最大区间长度。
3.边界处理：处理瓷砖合并时需注意边界条件，避免数组越界。

AC代码（如有雷同，纯属巧合）（改编自@狂火·维列）

#include <bits/stdc++.h>
using namespace std;
const int MAX = 1e5 + 7;

// 靴子结构体，存储步长、深度和原始索引
struct shoe {
    int step;
    int dep;
    int id;
} boo[MAX];

// 瓷砖结构体，存储积雪深度和原始索引
struct brick {
    int snow;
    int id;
} bri[MAX];

// 按积雪深度降序排序靴子
bool cmp1(shoe a, shoe b) {
    return a.dep > b.dep;
}

// 按积雪深度降序排序瓷砖
bool cmp2(brick a, brick b) {
    return a.snow > b.snow;
}

int cnt = 1;
int color[MAX], cross[MAX];  // color标记瓷砖是否可达，cross记录区间长度
int fa[MAX];  // 并查集父节点数组
int maxcross = 0;  // 当前最大不可达区间长度
int Cout[MAX];  // 存储每双靴子的答案

// 并查集查找操作，带路径压缩
inline int find(int x) {
    if (x == fa[x])
        return x;
    return fa[x] = find(fa[x]);
}

// 快速读入优化
int read() {
    int num = 0, bj = 0;
    char ch = getchar();
    while (!isdigit(ch)) {
        if (ch == '-')
            bj = 1;
        ch = getchar();
    }
    while (isdigit(ch)) {
        num = num * 10 + ch - '0';
        ch = getchar();
    }
    return bj ? -num : num;
}

int main() {
    int N, M;
    cin >> N >> M;
    
    // 读入瓷砖信息
    for (register int i = 1; i <= N; i++) {
        bri[i].snow = read();
        bri[i].id = i;
    }
    
    // 读入靴子信息
    for (register int i = 1; i <= M; i++) {
        boo[i].dep = read();
        boo[i].step = read();
        boo[i].id = i;
    }
    
    // 按积雪深度降序排序瓷砖和靴子
    sort(bri + 1, bri + 1 + N, cmp2);
    sort(boo + 1, boo + 1 + M, cmp1);
    
    // 初始化并查集
    for (register int i = 1; i <= N; i++) {
        cross[i] = 1;
        fa[i] = i;
    }
    
    // 处理每双靴子
    for (register int i = 1; i <= M; i++) {
        // 将所有积雪深度大于当前靴子s的瓷砖加入并查集
        while (cnt <= N && bri[cnt].snow > boo[i].dep) {
            maxcross = max(maxcross, 1);
            color[bri[cnt].id] = 1;  // 标记当前瓷砖为可达
            
            // 合并左边的区间
            if (color[bri[cnt].id - 1]) {
                int x = find(bri[cnt].id - 1), y = find(bri[cnt].id);
                fa[x] = y;
                cross[y] += cross[x];
                maxcross = max(maxcross, cross[y]);
            }
            
            // 合并右边的区间
            if (color[bri[cnt].id + 1]) {
                int x = find(bri[cnt].id), y = find(bri[cnt].id + 1);
                fa[x] = y;
                cross[y] += cross[x];
                maxcross = max(maxcross, cross[y]);
            }
            
            cnt++;
        }
        
        // 如果当前最大不可达区间长度小于靴子步长，则可以通过
        if (maxcross < boo[i].step) {
            Cout[boo[i].id] = 1;
        }
    }
    
    // 输出结果
    for (register int i = 1; i <= M; i++) {
        printf("%d\n", Cout[i]);
    }
}

复杂度分析

时间复杂度：排序操作 $O (N log N + B log B)$，处理每个瓷砖和靴子的操作近似 $O (N + B)$，总时间复杂度 $O (N log N + B log B)$。
空间复杂度：主要用于存储瓷砖、靴子和并查集，空间复杂度 $O (N + B)$。