#include <iostream> #include <vector> #include <algorithm> #include <deque> #include <set> #include <tuple> using namespace std; const int INF = 2e9; // ------------------------------------------------------------ // Segment Tree for Maximum values (finds value > x) // ------------------------------------------------------------ struct SegTreeMax { int n; vector<int> tree; SegTreeMax(const vector<int>& arr) { n = arr.size(); tree.resize(4 * n, -INF); build(1, 0, n - 1, arr); } void build(int node, int start, int end, const vector<int>& arr) { if (start == end) { tree[node] = arr[start]; } else { int mid = (start + end) / 2; build(2 * node, start, mid, arr); build(2 * node + 1, mid + 1, end, arr); tree[node] = max(tree[2 * node], tree[2 * node + 1]); } } // Find first index >= l with value > x // Returns n if not found int first_greater(int l, int x) { return _first_greater(1, 0, n - 1, l, x); } int _first_greater(int node, int start, int end, int l, int x) { // 如果当前区间完全在 l 左边，或者区间最大值都 <= x，直接返回无解 if (end < l || tree[node] <= x) { return n; } if (start == end) { return start; } int mid = (start + end) / 2; // 优先查左边 int res = _first_greater(2 * node, start, mid, l, x); if (res != n) return res; // 左边没找到查右边 return _first_greater(2 * node + 1, mid + 1, end, l, x); } }; // ------------------------------------------------------------ // Segment Tree for Minimum values (finds value <= x) // ------------------------------------------------------------ struct SegTreeMin { int n; vector<int> tree; SegTreeMin(const vector<int>& arr) { n = arr.size(); tree.resize(4 * n, INF); build(1, 0, n - 1, arr); } void build(int node, int start, int end, const vector<int>& arr) { if (start == end) { tree[node] = arr[start]; } else { int mid = (start + end) / 2; build(2 * node, start, mid, arr); build(2 * node + 1, mid + 1, end, arr); tree[node] = min(tree[2 * node], tree[2 * node + 1]); } } // Find first index >= l with value <= x // Returns n if not found int first_leq(int l, int x) { return _first_leq(1, 0, n - 1, l, x); } int _first_leq(int node, int start, int end, int l, int x) { if (end < l || tree[node] > x) { return n; } if (start == end) { return start; } int mid = (start + end) / 2; int res = _first_leq(2 * node, start, mid, l, x); if (res != n) return res; return _first_leq(2 * node + 1, mid + 1, end, l, x); } // Find last index <= r with value <= x // Returns -1 if not found int last_leq(int r, int x) { return _last_leq(1, 0, n - 1, r, x); } int _last_leq(int node, int start, int end, int r, int x) { if (start > r || tree[node] > x) { return -1; } if (start == end) { return start; } int mid = (start + end) / 2; // 优先尝试右边，因为我们要找的是 last (最大的 index) int res = -1; if (mid + 1 <= r) { // 只有右子树在范围内才尝试 res = _last_leq(2 * node + 1, mid + 1, end, r, x); } if (res != -1) return res; return _last_leq(2 * node, start, mid, r, x); } }; // ------------------------------------------------------------ // Global Data // ------------------------------------------------------------ int N, M; vector<int> T_arr; vector<int> H_arr; SegTreeMax* seg_max_ptr = nullptr; SegTreeMin* seg_min_ptr = nullptr; void initialize(vector<int> T, vector<int> H) { T_arr = T; H_arr = H; N = T.size(); M = H.size(); // 清理旧内存（如果是多组数据） if (seg_max_ptr) delete seg_max_ptr; if (seg_min_ptr) delete seg_min_ptr; seg_max_ptr = new SegTreeMax(T_arr); seg_min_ptr = new SegTreeMin(T_arr); } // ------------------------------------------------------------ // Query Logic // ------------------------------------------------------------ // Helper: 找到包含 row i 的自由区间的右端点 // 即找到 i 之后第一个障碍物的位置 - 1 int interval_end(int col, int i) { int blk = seg_min_ptr->first_leq(i + 1, H_arr[col]); return (blk == N) ? N - 1 : blk - 1; } bool can_reach(int L_ignore, int R_ignore, int S, int D) { if (S == D) return true; // 初始区间：列 S，包含行 0 int start_end = interval_end(S, 0); // BFS 队列: (col, L, R) deque<tuple<int, int, int>> q; q.push_back({S, 0, start_end}); // Visited: (col, L_start) // 使用 set 比较慢，如果 N*M 很大且内存允许，可用 vector<vector<bool>> set<pair<int, int>> visited; visited.insert({S, 0}); while (!q.empty()) { auto [col, Lint, Rint] = q.front(); q.pop_front(); // 检查是否到达目标 // 题目要求到达 (0, D)。如果当前区间在 D 列且包含 0 行 (Lint == 0)，则成功 if (col == D && Lint == 0) { return true; } // 尝试左右邻居 int neighbors[] = {col - 1, col + 1}; for (int nb : neighbors) { if (nb < 0 || nb >= M) continue; // 在邻居列 nb 中，寻找所有与 [Lint, Rint] 重叠的自由区间 // 从 Lint 开始寻找第一个自由行 (T > H[nb]) int y = seg_max_ptr->first_greater(Lint, H_arr[nb]); while (y != N && y <= Rint) { // 找到了一个重叠点 y，现在需要确定这个点所在的完整自由区间 [nb_start, nb_end] // 1. 找区间终点 int nb_end = interval_end(nb, y); // 2. 找区间起点 // 找到 y 及其上方最近的一个障碍物 int obstacle_above = seg_min_ptr->last_leq(y, H_arr[nb]); int nb_start = (obstacle_above != -1) ? obstacle_above + 1 : 0; if (visited.find({nb, nb_start}) == visited.end()) { visited.insert({nb, nb_start}); q.push_back({nb, nb_start, nb_end}); } // 继续在 [Lint, Rint] 范围内找下一个不连续的区间 // 从当前 nb 区间结束后的一行开始找 if (nb_end + 1 < N) { y = seg_max_ptr->first_greater(nb_end + 1, H_arr[nb]); } else { y = N; } } } } return false; }