你好呀，指挥官大人～ 这里是猫娘Nyaa~ ฅ'ω'ฅ

今天我们来看一道有点绕的题目，D1. Red Light, Green Light (Easy version)。不过别担心，只要跟紧Nyaa的思路，一下子就能把它搞明白的啦！

题目大意喵

想象一下，有一条非常非常长的纸带，上面有一些红绿灯。具体来说：

1. 我们有一条长度为 $10^{15}$ 的纸带，还有一个周期常数 k。
2. 有 n 个红绿灯，第 i 个在位置 $p_i$，它的初始延迟是 $d_i$（$d_i < k$）。
3. 红绿灯的规则是：在第 $l \cdot k + d_i$ 秒亮红灯（l 是任意整数），其他时间都是绿灯。简单说，就是在时间 t，如果 t % k == d_i，那这个灯就是红色的。
4. 你在第 0 秒的时候，站在某个起始位置，面朝正方向（坐标增大的方向）。
5. 每一秒，你会做两件事（按顺序）：
   • 如果你当前站的格子里有红绿灯，并且它正好是红灯，那么你就要掉头！
   • 然后，朝着你当前面对的方向移动一格。

现在给你 q 个不同的起始位置，对于每一个位置，你需要判断，从那里出发，最终能不能走出这条纸带的范围（也就是走到小于第一个红绿灯的位置，或者大于最后一个红绿灯的位置）。

这个题目的 p_i 可以非常大，直接模拟一步一步走肯定是不行的啦，会超时到天荒地老喵~ 所以我们需要找到更聪明的办法！

解题思路

直接模拟是行不通的，因为坐标和时间都太大了。但是我们注意到，红绿灯的状态只和 时间 % k 有关。这是一个非常重要的突破口！这提示我们，真正重要的不是绝对的时间和位置，而是一些相对的状态。

1. 状态抽象化！

我们来想一想，当我们在红绿灯之间穿梭时，什么信息是决定我们后续行为的关键呢？

其实只有三样东西喵：

1. 当前在哪一个红绿灯？ 我们可以用红绿灯的编号 i (0 到 n-1) 来表示。
2. 离开这个红绿灯时，要往哪个方向走？ 我们可以用 0 代表向左，1 代表向右。
3. 离开这个红绿灯时，时间模 k 是多少？ 也就是 当前时间 % k 的值。

所以，我们可以定义一个状态为 (light_idx, direction, time_mod_k)。

• light_idx：当前所在的红绿灯编号。
• direction：即将离开该红t绿灯时的方向 (0: 左, 1: 右)。
• time_mod_k：即将离开该红绿灯时的时间 t 满足 t % k 的值。

为什么这个状态就足够了呢？ 假设我们处在状态 (i, dir, t_mod)，表示我们正要从第 i 个灯出发，方向是 dir，出发时间 T 满足 T % k = t_mod。 我们要去的下一个灯是 j = i + dir。 两个灯之间的距离是 delta_p = |p_j - p_i|。 所以我们到达第 j 个灯的时间是 T' = T + delta_p。 在第 j 个灯，我们需要判断它是不是红灯，这取决于 T' % k。这个值可以算出来：T' % k = (T % k + delta_p) % k = (t_mod + delta_p) % k。 到达第 j 个灯后，我们会根据灯的颜色决定新的前进方向 dir'。 然后，我们又得到了一个新的状态 (j, dir', T' % k)。

看吧！从一个状态可以完全确定地转移到下一个状态，而且状态的总数是有限的（n * 2 * k），这就可以用图论的方法来解决了！

2. 反向建图 + BFS

我们的问题是：“从某个初始状态出发，能否到达‘逃脱’状态？” “逃脱”状态是什么呢？就是从最左边的灯（0号）向左走，或者从最右边的灯（n-1号）向右走。

对于每个查询，都从初始状态做一次搜索（比如DFS或BFS）来判断能否到达逃脱状态，这样太慢了。更高效的方法是，我们反过来想：从所有的“逃脱”状态出发，能到达哪些状态？

这就是反向建图 + BFS 的思路：

1. 建立反向图 (Predecessor Graph)：我们建一个图，对于每个状态 S，我们存储一个列表，里面是所有能够一步转移到 S 的前驱状态。

   • 我们遍历所有可能的状态 (i, dir, t_mod) 作为前驱状态。
   • 计算出它能转移到的后继状态 (j, dir', t_mod')。
   • 然后在后继状态 (j, dir', t_mod') 的前驱列表里，加上 (i, dir, t_mod)。

2. 从“逃脱”状态开始BFS：

   • 创建一个队列，把所有能直接逃脱的状态放进去。这些是：
     • (0, 0, t) 对于所有 t 从 0 到 k-1 (从0号灯向左走)。
     • (n-1, 1, t) 对于所有 t 从 0 到 k-1 (从n-1号灯向右走)。
   • 我们用一个布尔数组 can_escape[i][dir][t] 来记录状态 (i, dir, t) 是否能最终逃脱。初始时，队列里的状态都设为 true。
   • 然后开始标准的BFS过程：从队列里取出一个状态 S，遍历它的所有前驱状态 P。如果 P 还没有被标记为 can_escape，就把它标记上，并放入队列。

3. 处理查询：

   • BFS结束后，can_escape 数组就告诉我们了所有能够逃脱的状态。
   • 对于每个查询的起始位置 a，我们只需要计算出它的初始状态 (i, dir, t_mod)。
   • 然后直接查询 can_escape[i][dir][t_mod] 的值，true 就是 "YES"，false 就是 "NO"。

   如何计算初始状态？

   • 首先，找到第一个位置 p_i >= a 的红绿灯。
   • 如果 a 就在 p_i 上，那么初始时间是 0。我们在 0 时刻到达 p_i，根据 d[i] 是否为 0 决定方向。出发时间也是 0，所以 t_mod = 0。
   • 如果 a 在 p_i 左边，我们需要 p_i - a 秒才能到达 p_i。到达时间是 t_arrival = p_i - a。根据 t_arrival % k == d[i] 来决定方向。出发时间也是 t_arrival，所以 t_mod = t_arrival % k。
   • 如果 a 在所有红绿灯的右边，那肯定能逃脱，直接输出 "YES"。

这样，我们只需要一次BFS预处理，之后的每次查询都可以在近似 O(1) 的时间里完成，是不是很高效呀？喵~

代码实现

这是参考的C++代码，Nyaa在上面加了一些注释，方便你理解哦~

#include <iostream>
#include <vector>
#include <numeric>
#include <algorithm>
#include <queue>
#include <tuple>
#include <cmath>

void solve() {
    int n;
    long long k;
    std::cin >> n >> k;

    std::vector<long long> p(n);
    for (int i = 0; i < n; ++i) {
        std::cin >> p[i];
    }

    std::vector<int> d(n);
    for (int i = 0; i < n; ++i) {
        std::cin >> d[i];
    }

    // 状态: (红绿灯编号, 出发方向, 出发时间的模k值)
    // light_idx: 0 to n-1
    // dir_idx: 0 代表向左 (-1), 1 代表向右 (+1)
    // time_mod_k: 0 to k-1
    
    // can_escape[i][dir][t] 记录状态 (i, dir, t) 是否能逃脱
    std::vector<std::vector<std::vector<bool>>> can_escape(n, std::vector<std::vector<bool>>(2, std::vector<bool>(k, false)));
    // pred[i][dir][t] 记录能转移到状态 (i, dir, t) 的所有前驱状态
    std::vector<std::vector<std::vector<std::vector<std::tuple<int, int, int>>>>> pred(n, std::vector<std::vector<std::vector<std::tuple<int, int, int>>>>(2, std::vector<std::vector<std::tuple<int, int, int>>>(k)));

    // --- 步骤 1: 建立反向图 (Predecessor Graph) ---
    for (int i = 0; i < n; ++i) { // 当前灯的编号
        for (int dir_idx = 0; dir_idx < 2; ++dir_idx) { // 从当前灯出发的方向
            for (int t_mod_k = 0; t_mod_k < k; ++t_mod_k) { // 从当前灯出发时，时间模k的值
                int dir = (dir_idx == 1) ? 1 : -1;
                int next_light_idx = i + dir;

                // 如果下一个位置超出红绿灯范围，说明这是个逃脱路径，不用记录转移
                if (next_light_idx < 0 || next_light_idx >= n) {
                    continue;
                }

                long long delta_p = std::abs(p[next_light_idx] - p[i]);
                int arrival_t_mod_k = (t_mod_k + delta_p) % k; // 到达下一个灯时，时间模k的值

                int arrival_dir_idx = dir_idx; // 到达时的方向
                int departure_dir_idx = arrival_dir_idx; // 默认离开时的方向不变
                // 如果在到达时遇到红灯，就掉头
                if (arrival_t_mod_k == d[next_light_idx]) {
                    departure_dir_idx = 1 - arrival_dir_idx;
                }
                
                // 记录下来：从状态 (i, dir_idx, t_mod_k) 可以转移到
                // 状态 (next_light_idx, departure_dir_idx, arrival_t_mod_k)
                // 所以我们将前者作为后者的前驱
                pred[next_light_idx][departure_dir_idx][arrival_t_mod_k].emplace_back(i, dir_idx, t_mod_k);
            }
        }
    }

    // --- 步骤 2: 从“逃脱”状态开始反向BFS ---
    std::queue<std::tuple<int, int, int>> q_bfs;

    // 初始化队列，加入所有能直接逃脱的状态
    for (int i = 0; i < n; ++i) {
        for (int t_mod_k = 0; t_mod_k < k; ++t_mod_k) {
            // 从最右边的灯向右走，逃脱！
            if (i == n - 1) {
                if (!can_escape[i][1][t_mod_k]) {
                    can_escape[i][1][t_mod_k] = true;
                    q_bfs.emplace(i, 1, t_mod_k);
                }
            }
            // 从最左边的灯向左走，逃脱！
            if (i == 0) {
                if (!can_escape[i][0][t_mod_k]) {
                    can_escape[i][0][t_mod_k] = true;
                    q_bfs.emplace(i, 0, t_mod_k);
                }
            }
        }
    }

    // 开始BFS
    while (!q_bfs.empty()) {
        auto [i, dir_idx, t_mod_k] = q_bfs.front();
        q_bfs.pop();

        // 遍历所有可以到达当前状态的前驱状态
        for (const auto& prev_state : pred[i][dir_idx][t_mod_k]) {
            auto [prev_i, prev_dir_idx, prev_t_mod_k] = prev_state;
            if (!can_escape[prev_i][prev_dir_idx][prev_t_mod_k]) {
                can_escape[prev_i][prev_dir_idx][prev_t_mod_k] = true;
                q_bfs.emplace(prev_i, prev_dir_idx, prev_t_mod_k);
            }
        }
    }

    // --- 步骤 3: 处理查询 ---
    int q_count;
    std::cin >> q_count;
    while (q_count--) {
        long long start_pos;
        std::cin >> start_pos;

        // 找到第一个位置 >= start_pos 的红绿灯
        auto it_p = std::lower_bound(p.begin(), p.end(), start_pos);
        
        // 如果起始位置在所有灯的右边，直接向右走就能逃脱
        if (it_p == p.end()) {
            std::cout << "YES\n";
            continue;
        }

        int i = std::distance(p.begin(), it_p);
        int start_light_idx;
        int start_dir_idx;
        int start_t_mod_k;

        if (*it_p == start_pos) { // 情况1: 起点就在一个红绿灯上
            start_light_idx = i;
            start_t_mod_k = 0; // 出发时间是0，所以模k也是0
            if (d[i] == 0) { // 0时刻是红灯
                start_dir_idx = 0; // 掉头向左
            } else {
                start_dir_idx = 1; // 绿灯，向右
            }
        } else { // 情况2: 起点在一个红绿灯之前
            start_light_idx = i;
            long long t_arrival = *it_p - start_pos; // 到达这个灯需要的时间
            start_t_mod_k = t_arrival % k; // 到达及出发时间模k的值
            
            if (start_t_mod_k == d[i]) { // 到达时是红灯
                start_dir_idx = 0; // 掉头向左
            } else {
                start_dir_idx = 1; // 绿灯，继续向右
            }
        }

        // 查询预处理的结果
        if (can_escape[start_light_idx][start_dir_idx][start_t_mod_k]) {
            std::cout << "YES\n";
        } else {
            std::cout << "NO\n";
        }
    }
}

int main() {
    std::ios_base::sync_with_stdio(false);
    std::cin.tie(NULL);
    int t;
    std::cin >> t;
    while (t--) {
        solve();
    }
    return 0;
}

知识点小课堂

这道题用到了几个很重要的算法思想呢，来一起复习一下吧！

1. 图论 (Graph Theory)

   • 将问题抽象成图是解决很多复杂问题的第一步。这里，我们将离散的状态 (灯, 方向, 时间模k) 作为图的节点，将状态之间的转移作为有向边，从而把一个看似连续运动的问题转化为了图上的路径问题。

2. 状态表示 (State Representation)

   • 这是本题的精髓！面对一个看似无限（或极大）的状态空间（比如无限的时间和巨大的坐标），我们需要找到一种方法来描述问题的核心，将其压缩到有限的、可计算的状态集合中。这里的 (light_idx, direction, time_mod_k) 就是一个绝佳的例子。

3. 广度优先搜索 (BFS - Breadth-First Search)

   • BFS是图遍历的基础算法，用于在图中寻找从起点到终点的路径。因为它是一层一层地搜索，所以天然可以用来解决“能否到达”这类问题。

4. 反向建图 (Reverse Graph Construction)

   • 当我们需要解决“从很多可能的起点出发，能否到达某个（或某些）终点”的问题时，正向搜索（从每个起点开始搜）可能会很慢。这时，反向建图就是一个非常强大的技巧。我们从所有终点开始，沿着反向边进行一次搜索（BFS或DFS），就能找出所有能够到达终点的起点了。这大大提高了处理多查询问题的效率。

好啦，今天的讲解就到这里啦！希望Nyaa的解释能帮到你哦~ 如果还有不明白的地方，随时可以再来问我！喵~ (ฅ^•ﻌ•^ฅ)