HoppingRabbit - 题解

标签与难度

标签: 扫描线, 线段树, 模运算, 计算几何, 数据结构, 坐标变换难度: 2100

题目大意喵~

你好呀，指挥官！这里是聪明的我，准备好和我一起解决这个有趣的问题了吗？喵~

这道题是关于一只可爱的小兔子，它在一片布满了矩形陷阱的草地上跳跃。

兔子的跳跃: 小兔子只能沿着 x 轴或 y 轴方向跳，而且每次跳跃的距离都是固定的 $d$ 。
兔子的位置: 它的起始位置是 $(x_0+0.5, y_0+0.5)$ ，其中 $x_0$ 和 $y_0$ 是整数。这意味着它总是在格子线的正中间起跳和降落。
陷阱: 陷阱是 $n$ 个坐标轴平行的矩形，由左下角 $(x_1, y_1)$ 和右上角 $(x_2, y_2)$ 定义。一个点 $(x,y)$ 在陷阱里，当且仅当 $x_1 \le x < x_2$ 且 $y_1 \le y < y_2$ 。
目标: 我们需要帮小兔子找到一个初始的整数坐标 $(x_0, y_0)$ ，使得从 $(x_0+0.5, y_0+0.5)$ 出发，无论怎么跳，它永远不会降落在任何一个陷阱里。只要找到一个这样的点就行啦！

解题思路分析

这道题看起来是在一个无限大的平面上寻找安全点，感觉好复杂哦！但是别怕，我我最擅长发现问题中的小秘密了，喵~

第一步：把无限变有限，喵！

我们来观察一下小兔子的移动规律。如果它从 $(x_0+0.5, y_0+0.5)$ 开始跳，经过任意次跳跃，它的新位置一定是 $(x_0+0.5 + k_x \cdot d, y_0+0.5 + k_y \cdot d)$ ，其中 $k_x$ 和 $k_y$ 是某些整数。

小兔子降落点的整数部分坐标是 $(x_0 + k_x \cdot d, y_0 + k_y \cdot d)$ 。我们来看看这些坐标对 $d$ 取模的结果：

(x_0 + k_x \cdot d) \pmod d \equiv x_0 \pmod d

(y_0 + k_y \cdot d) \pmod d \equiv y_0 \pmod d

看到了吗？无论小兔子怎么跳，它降落点的整数坐标 $(X, Y)$ 永远满足 $X \equiv x_0 \pmod d$ 和 $Y \equiv y_0 \pmod d$ 。

这意味着，我们选择了一个初始的 $(x_0, y_0)$ ，就等于选择了一个固定的余数对 $(x_0 \pmod d, y_0 \pmod d)$ 。所有可达的格子构成了一个以 $d$ 为周期的网格。

所以，我们的问题就从在无限平面上找一个安全点，简化为在一个 $d \times d$ 的 "余数网格" 中，找到一个安全的余数对 $(x_{rem}, y_{rem})$ ，其中 $0 \le x_{rem}, y_{rem} < d$ 。只要找到了，我们就可以直接输出 $(x_{rem}, y_{rem})$ 作为答案！是不是一下子清晰多啦？

第二步：识别出“禁区”，喵！

一个余数对 $(x_{rem}, y_{rem})$ 是“危险”的，当且仅当存在某个陷阱，使得这个陷阱同时覆盖了 x 坐标余数为 $x_{rem}$ 的某些整数，和 y 坐标余数为 $y_{rem}$ 的某些整数。

对于一个陷阱，由 $[x_1, x_2)$ 和 $[y_1, y_2)$ 定义，我们来分析它会“封禁”哪些余数。

X 坐标: 陷阱会封禁所有满足 $x \in [x_1, x_2)$ 的整数 $x$ 的余数 $x \pmod d$ 。我们把这些被封禁的 x 余数集合记为 $S_x$ 。
Y 坐标: 同理，陷阱会封禁所有满足 $y \in [y_1, y_2)$ 的整数 $y$ 的余数 $y \pmod d$ 。我们把这些被封禁的 y 余数集合记为 $S_y$ 。

那么，一个余数对 $(x_{rem}, y_{rem})$ 就被这个陷阱封禁了，当且仅当 $x_{rem} \in S_x$ 并且 $y_{rem} \in S_y$ 。

$S_x$ 和 $S_y$ 是什么样子的呢？

如果陷阱的宽度 $x_2 - x_1 \ge d$ ，那么它会覆盖所有 $d$ 种 x 余数，即 $S_x = \{0, 1, \dots, d-1\}$ 。
如果宽度 $x_2 - x_1 < d$ $x_{2} - x_{1} < d$ ，设 $x_1' = x_1 \pmod d$ $x_{1}^{'} = x_{1} (mod d)$ 和 $x_2' = (x_2-1) \pmod d$ $x_{2}^{'} = (x_{2} - 1) (mod d)$ 。
- 如果 $x_1' \le x_2'$ , 那么 $S_x$ 就是一个连续的区间 $[x_1', x_2']$ 。
- 如果 $x_1' > x_2'$ , 这说明余数区间“环绕”了，比如从 $d-2$ 到 $1$ 。这时 $S_x$ 分裂成两个区间： $[0, x_2']$ 和 $[x_1', d-1]$ 。

对 $S_y$ 也是一样的分析。所以，每个陷阱都在我们的 $d \times d$ 余数网格上定义了一片“禁区”，这片禁区是由最多 $2 \times 2 = 4$ 个小矩形组成的。

我们的任务就是判断，这 $n$ 个陷阱产生的所有禁区矩形，有没有把整个 $d \times d$ 的网格完全覆盖。只要有一个格子没被覆盖，我们就找到了答案！

第三步：用扫描线和线段树找到安全的“缝隙”，喵！

现在问题变成了：在 $d \times d$ 的网格上，有若干个矩形，问是否存在一个点没被任何矩形覆盖。这是一个经典的计算几何问题，可以用扫描线算法高效解决！

想象我们有一条垂直的扫描线，从 $x=0$ 扫到 $x=d-1$ 。

事件: 对于每一个禁区矩形 $[x_s, x_e] \times [y_s, y_e]$ $[x_{s}, x_{e}] \times [y_{s}, y_{e}]$ ，我们创建两个事件：
- 在 $x=x_s$ 处，有一个“开始”事件，表示从现在起，y 轴上的 $[y_s, y_e]$ 区间被覆盖了。
- 在 $x=x_e+1$ 处，有一个“结束”事件，表示 y 轴上的 $[y_s, y_e]$ 区间的这个覆盖消失了。
状态维护: 当扫描线在某个位置 $x$ 时，我们需要知道 y 轴上 $[0, d-1]$ 的每个点被多少个“有效”的矩形覆盖。这个信息可以用一棵线段树来维护！
线段树: 我们建立一棵线段树，管理 y 轴上的区间 $[0, d-1]$ $[0, d - 1]$ 。
- 树的每个节点维护两个值：min_coverage (该节点代表的y轴区间的最小覆盖次数) 和 lazy_add (懒惰标记，用于区间更新)。
- 当扫描线遇到“开始”事件（矩形 $[x_s, x_e] \times [y_s, y_e]$ ），我们对线段树中 $[y_s, y_e]$ 区间执行“加1”操作。
- 当遇到“结束”事件，我们对相应区间执行“减1”操作。
寻找答案: 在扫描线移动到每个整数位置 $x$ $x$ (从 $0$ $0$ 到 $d-1$ $d - 1$ ) 时，我们先处理完所有在 $x$ $x$ 处的事件，然后查询线段树的树根。
- 如果树根的 min_coverage 值为 $0$ ，这说明在当前的 x 坐标下，y 轴上至少有一个点的覆盖次数是 $0$ ！太棒了，我们找到了一个安全的缝隙！这个 $x$ 就是我们答案的 x 坐标。
- 为了找到对应的 y 坐标，我们可以在线段树中从根节点向下查询，专门走 min_coverage 为 $0$ 的分支，直到叶子节点，就能找到一个安全的 y 坐标。
- 如果扫描线从 $0$ 扫到 $d-1$ 都没发现 min_coverage 为 $0$ 的情况，那就说明整个 $d \times d$ 网格都被禁区覆盖了，只能遗憾地告诉小兔子 "NO" 了。

这个方法结合了坐标变换、扫描线和线段树，是不是很酷？喵~ 让我们来实现它吧！

代码实现

这是我根据上面的思路，精心重构的一份代码哦！注释超详细的，希望能帮到你，喵~

cpp

#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;

const long long INF = 2e9; // 一个足够大的数

// 线段树节点
struct Node {
    int min_coverage; // 区间内最小覆盖次数
    int lazy_add;     // 懒惰标记
};

vector<Node> seg_tree;
int d_val; // 全局变量存储d的值

// 更新节点信息
void push_up(int p) {
    seg_tree[p].min_coverage = min(seg_tree[2 * p].min_coverage, seg_tree[2 * p + 1].min_coverage);
}

// 下推懒惰标记
void push_down(int p) {
    if (seg_tree[p].lazy_add != 0) {
        // 更新左子节点
        seg_tree[2 * p].min_coverage += seg_tree[p].lazy_add;
        seg_tree[2 * p].lazy_add += seg_tree[p].lazy_add;
        // 更新右子节点
        seg_tree[2 * p + 1].min_coverage += seg_tree[p].lazy_add;
        seg_tree[2 * p + 1].lazy_add += seg_tree[p].lazy_add;
        // 清除当前节点的懒惰标记
        seg_tree[p].lazy_add = 0;
    }
}

// 构建线段树
void build(int p, int l, int r) {
    seg_tree[p] = {0, 0};
    if (l == r) {
        return;
    }
    int mid = l + (r - l) / 2;
    build(2 * p, l, mid);
    build(2 * p + 1, mid + 1, r);
}

// 区间更新
void update(int p, int l, int r, int update_l, int update_r, int val) {
    if (update_l <= l && r <= update_r) {
        seg_tree[p].min_coverage += val;
        seg_tree[p].lazy_add += val;
        return;
    }
    push_down(p);
    int mid = l + (r - l) / 2;
    if (update_l <= mid) {
        update(2 * p, l, mid, update_l, update_r, val);
    }
    if (update_r > mid) {
        update(2 * p + 1, mid + 1, r, update_l, update_r, val);
    }
    push_up(p);
}

// 查找一个覆盖次数为0的y坐标
int find_zero_y(int p, int l, int r) {
    if (l == r) {
        return l;
    }
    push_down(p);
    int mid = l + (r - l) / 2;
    if (seg_tree[2 * p].min_coverage == 0) {
        return find_zero_y(2 * p, l, mid);
    } else {
        return find_zero_y(2 * p + 1, mid + 1, r);
    }
}

// 扫描线事件
struct Event {
    int y_start, y_end, val;
};

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);

    int n;
    cin >> n >> d_val;

    // 事件列表，events[x]存储在x坐标处发生的所有事件
    vector<vector<Event>> events(d_val + 1);

    for (int i = 0; i < n; ++i) {
        long long x1, y1, x2, y2;
        cin >> x1 >> y1 >> x2 >> y2;
        
        // 题目给的是[x1, x2), [y1, y2)的整数点，我们处理[x1, x2-1], [y1, y2-1]
        x2--; 
        y2--;

        vector<pair<int, int>> x_intervals, y_intervals;

        // 计算x轴上的禁区余数区间
        if (x2 - x1 + 1 >= d_val) {
            x_intervals.push_back({0, d_val - 1});
        } else {
            // 使用 (val % d + d) % d 来确保结果是正数
            int rem_x1 = (x1 % d_val + d_val) % d_val;
            int rem_x2 = (x2 % d_val + d_val) % d_val;
            if (rem_x1 <= rem_x2) {
                x_intervals.push_back({rem_x1, rem_x2});
            } else {
                x_intervals.push_back({0, rem_x2});
                x_intervals.push_back({rem_x1, d_val - 1});
            }
        }

        // 计算y轴上的禁区余数区间
        if (y2 - y1 + 1 >= d_val) {
            y_intervals.push_back({0, d_val - 1});
        } else {
            int rem_y1 = (y1 % d_val + d_val) % d_val;
            int rem_y2 = (y2 % d_val + d_val) % d_val;
            if (rem_y1 <= rem_y2) {
                y_intervals.push_back({rem_y1, rem_y2});
            } else {
                y_intervals.push_back({0, rem_y2});
                y_intervals.push_back({rem_y1, d_val - 1});
            }
        }

        // 将禁区矩形转化为扫描线事件
        for (const auto& x_int : x_intervals) {
            for (const auto& y_int : y_intervals) {
                if (y_int.first <= y_int.second) {
                    events[x_int.first].push_back({y_int.first, y_int.second, 1});
                    events[x_int.second + 1].push_back({y_int.first, y_int.second, -1});
                }
            }
        }
    }

    // 初始化线段树
    seg_tree.resize(4 * d_val);
    build(1, 0, d_val - 1);

    // 开始扫描！
    for (int x = 0; x < d_val; ++x) {
        // 处理当前x坐标的所有事件
        for (const auto& event : events[x]) {
            update(1, 0, d_val - 1, event.y_start, event.y_end, event.val);
        }

        // 查询是否存在安全点
        if (seg_tree[1].min_coverage == 0) {
            cout << "YES" << endl;
            int y = find_zero_y(1, 0, d_val - 1);
            cout << x << " " << y << endl;
            return 0;
        }
    }

    // 扫描结束都没有找到
    cout << "NO" << endl;

    return 0;
}

复杂度分析

时间复杂度: $O((N+D) \log D)$
- 事件处理: 每个陷阱最多产生4个禁区矩形，每个矩形产生2个事件。所以总事件数是 $O(N)$ 。将这些事件放入对应的 events 数组中需要 $O(N)$ 的时间。
- 扫描过程: 我们有一个从 $0$ 到 $d-1$ 的主循环，共 $D$ 次迭代（这里用 $D$ 代表变量 d_val）。
- 在整个扫描过程中，我们总共要处理 $O(N)$ 个事件。每个事件都是一次线段树的区间更新，耗时 $O(\log D)$ 。所以所有事件更新的总时间是 $O(N \log D)$ 。
- 在每次主循环迭代中，我们还要查询一次线段树的根（ $O(1)$ ）和可能的一次查找 ( $O(\log D)$ )。这部分总共是 $O(D \log D)$ 。
- 所以，总的时间复杂度是 $O(N \log D + D \log D) = O((N+D) \log D)$ 。
空间复杂度: $O(N+D)$
- 事件存储: events 数组需要 $O(N)$ 的空间来存储所有事件。
- 线段树: 线段树需要 $O(D)$ 的空间。
- 因此，总空间复杂度为 $O(N+D)$ 。

知识点总结

这道题真是一次精彩的冒险，不是吗？我们用到了好几个强大的工具呢！

模运算 (Modulo Arithmetic): 它是我们解题的第一把钥匙！通过取模，我们成功地将一个无限大的问题域映射到了一个有限的 $d \times d$ 网格上，大大简化了问题。
扫描线算法 (Sweep Line): 这是处理二维平面问题的经典思想。通过将静态的二维问题转化为一维扫描过程中的动态问题，我们可以更方便地进行分析和计算。
线段树 (Segment Tree): 作为扫描线的得力助手，线段树在这里被用来高效地维护一维区间上的信息（覆盖次数）。它的区间更新和查询能力是整个算法的核心。
问题转化: 整个解题过程就是一个不断转化的过程。从物理的兔子跳跃，到数学的同余关系，再到几何的矩形覆盖，最后到算法的扫描线模型。这种抽象和转化的能力在算法竞赛中可是非常重要的哦，喵~

希望这次的题解能让你有所收获！下次有难题，也随时可以来找我玩呀！喵~

HoppingRabbit - 题解 ​

标签与难度 ​

题目大意喵~ ​

解题思路分析 ​

第一步：把无限变有限，喵！ ​

第二步：识别出“禁区”，喵！ ​

第三步：用扫描线和线段树找到安全的“缝隙”，喵！ ​

代码实现 ​

复杂度分析 ​

知识点总结 ​