#include <vector> #include <algorithm> #include <cmath> #include <climits> using namespace std; const int MAXM = 200005; const int LOGM = 19; int st[MAXM][LOGM]; int logs[MAXM]; int global_max_reachable_T = -1; void initialize(std::vector<int> T, std::vector<int> H) { int N = T.size(); int M = H.size(); logs[1] = 0; for (int i = 2; i <= M; i++) { logs[i] = logs[i / 2] + 1; } for (int i = 0; i < M; i++) { st[i][0] = H[i]; } for (int j = 1; j < LOGM; j++) { for (int i = 0; i + (1 << j) <= M; i++) { st[i][j] = max(st[i][j - 1], st[i + (1 << (j - 1))][j - 1]); } } int min_H = INT_MAX; for (int x : H) { if (x < min_H) min_H = x; } global_max_reachable_T = -1; for (int i = 0; i < N; i++) { if (T[i] <= min_H) { break; } if (T[i] > global_max_reachable_T) { global_max_reachable_T = T[i]; } } } // --------------------------------------------------------- // can_reach 函数 // --------------------------------------------------------- bool can_reach(int L, int R, int S, int D) { int left = S, right = D; if (left > right) swap(left, right); int len = right - left + 1; int k = logs[len]; int max_obstacle_H = max(st[left][k], st[right - (1 << k) + 1][k]); if (global_max_reachable_T > max_obstacle_H) { return true; } else { return false; } }