洛谷 P4269 分析（别看）

科技起源的小号1

2026-10-11 20:50:05

发布于：天津

9阅读

0回复

0点赞

原题链接

1 题目

1.1 题目所需求出内容

对于本题，最终要求：可行性

1.2 题目背景、允许、禁止与限制

背景：
有 $n$ 块地砖，第 $i$ 块地砖有一个深度 $f_i$
有 $b$ 双靴子，其中每一双靴子有两个信息 $(s_i,d_i)$ ，分别代表靴子的最大深度及最远跳跃距离
允许：
对于每双靴子，检查其是否能从第 $1$ 块地砖走到第 $n$ 块（只能踩在 $s_i<f_i$ 的地砖上且每次至多前进 $d_i$ 步）

1.3 题目数据范围与猜测

$n,b\le10^5\to O(b~log~n)$

1.4 一句话概括题意

有 $n$ 个点，每个点有一个值，对于每个给定信息，检查其跳跃距离与积雪承受深度能否使其从 $1$ 跳到 $n$

2 题目破题推导

2.1 第一步：正向思维转逆向思维

正向思维：
对每个靴子都尝试走一遍地砖，时间复杂度 $O(nb)$
逆向思维：
简化一下问题可以解释成：对于每双鞋 $(d_i,s_i)$ ，检查序列 $f$ 中是否存在一段 $\ge d_i$ 且 $>s_i$ 的连续区间

2.2 第二步：单调性思考

关键点：连续段落的长度
考虑单调性：深度更小的鞋，这个连续区间就一定 $\ge$ 深度更大的鞋
因此维护完深度更大的鞋子的连续段落后，深度更小的鞋一定是在连续段落的基础上扩展

3 模型匹配

既然有了单调性，肯定先维护深度更大的鞋子（ $\huge{排序}$ ）
在所有段落在当前基础上扩展（ $\huge{并查集}$ ）对于新的鞋，每当产生一个新的不能踩的点，与其相邻两个节点（是位置相邻而非大小关系相邻）合并，如果左右都没有，那就是一个距离为 $1$ 的连续区间。而如果某一边有，就是合并左右两边并且更新最长距离
为了辅助并查集，需要按点的深度从大到小排序，这样当前能不能踩的状态一定由上一双靴子最后一个能踩的点往后延伸（保证每双鞋不用单独扫描一遍）
并且因为有了单调性，所以复杂度是 $O(n~log~n+(n+b)+n(\alpha(n)))$

4 最终代码（禁止抄袭，仅用于参考）

#include <bits/stdc++.h>
using namespace std;

int n, b;
const int N = 1e5 + 10;
struct node{
    int dep, step;
    int idx;
}a[N];
bool cmp(node x, node y){
    return x.dep > y.dep;
}
struct node2{
    int dep;
    int idx;
}f[N];
bool cmp2(node2 x, node2 y){
    return x.dep > y.dep;
}

int fa[N], num[N];
void init(){
    for (int i = 1;i <= n;i++){
        fa[i] = i;
    }
}
int get(int x){
    if (fa[x] != x){
        fa[x] = get(fa[x]);
    }
    return fa[x];
}
int mx = INT_MIN;
void merge(int x, int y){
    x = get(x);
    y = get(y);
    if (x != y){
        fa[x] = y;// 注意更新num的逻辑
        num[y] += num[x];
        mx = max(mx, num[y]);
    }
}
bool vis[N];
int ans[N];

int main(){

    cin >> n >> b;
    init();
    for (int i = 1;i <= n;i++){
        cin >> f[i].dep;
        f[i].idx = i;
    }
    for (int i = 1;i <= b;i++){
        cin >> a[i].dep >> a[i].step;
        a[i].idx = i;
    }
    sort(a + 1, a + 1 + b, cmp);
    sort(f + 2, f + n, cmp2);
    int j = 2;
    for (int i = 1;i <= b;i++){
        while (a[i].dep < f[j].dep && j < n){
            vis[f[j].idx] = true;
            num[f[j].idx] = 1;
            if (vis[f[j].idx - 1]){
                merge(f[j].idx - 1, f[j].idx);
            }
            if (vis[f[j].idx + 1]){
                merge(f[j].idx + 1, f[j].idx);
            }
            j++;
            mx = max(mx, 1);
        }
        ans[a[i].idx] = (a[i].step > mx);
    }
    for (int i = 1;i <= b;i++){
        cout << ans[i] << endl;
    }
    
    return 0;
}