#include <vector>
#include <algorithm>
#include <cmath>
using namespace std;
int N, M;
vector<int> T_val, H_val;
vector<int> P;
vector<int> MaxT;
vector<int> global_reach;
const int MAXM = 200005;
const int LOGM = 19;
int max_st[LOGM][MAXM];
int min_idx_st[LOGM][MAXM];
int log_table[MAXM];
void build_sparse_table() {
log_table[1] = 0;
for (int i = 2; i <= M; i++) {
log_table[i] = log_table[i / 2] + 1;
}
for (int i = 0; i < M; i++) {
max_st[0][i] = H_val[i];
min_idx_st[0][i] = i;
}
for (int j = 1; j < LOGM; j++) {
for (int i = 0; i + (1 << j) <= M; i++) {
max_st[j][i] = max(max_st[j - 1][i], max_st[j - 1][i + (1 << (j - 1))]);
int left_idx = min_idx_st[j - 1][i];
int right_idx = min_idx_st[j - 1][i + (1 << (j - 1))];
if (H_val[left_idx] <= H_val[right_idx]) {
min_idx_st[j][i] = left_idx;
} else {
min_idx_st[j][i] = right_idx;
}
}
}
}
int query_max(int L, int R) {
int j = log_table[R - L + 1];
return max(max_st[j][L], max_st[j][R - (1 << j) + 1]);
}
int query_min_idx(int L, int R) {
int j = log_table[R - L + 1];
int left_idx = min_idx_st[j][L];
int right_idx = min_idx_st[j][R - (1 << j) + 1];
if (H_val[left_idx] <= H_val[right_idx]) return left_idx;
return right_idx;
}
int get_F(int h) {
int l = 0, r = N - 1, ans = N;
while (l <= r) {
int mid = l + (r - l) / 2;
if (P[mid] <= h) {
ans = mid;
r = mid - 1;
} else {
l = mid + 1;
}
}
if (ans == 0) return 0;
return MaxT[ans - 1];
}
int get_left(int curr, int limit, int L_bound) {
int l = L_bound, r = curr, ans = curr;
while (l <= r) {
int mid = l + (r - l) / 2;
if (query_max(mid, curr) < limit) {
ans = mid;
r = mid - 1;
} else {
l = mid + 1;
}
}
return ans;
}
int get_right(int curr, int limit, int R_bound) {
int l = curr, r = R_bound, ans = curr;
while (l <= r) {
int mid = l + (r - l) / 2;
if (query_max(curr, mid) < limit) {
ans = mid;
l = mid + 1;
} else {
r = mid - 1;
}
}
return ans;
}
int simulate(int S, int L, int R, int req) {
int curr = S;
int curr_h = H_val[S];
while (true) {
int T_curr = get_F(curr_h);
if (T_curr > req) return T_curr;
int l = get_left(curr, T_curr, L);
int r = get_right(curr, T_curr, R);
int nxt = query_min_idx(l, r);
if (nxt == curr) return T_curr;
curr = nxt;
curr_h = H_val[curr];
}
}
void initialize(std::vector<int> T, std::vector<int> H) {
N = T.size();
M = H.size();
T_val = T;
H_val = H;
P.resize(N);
MaxT.resize(N);
P[0] = T[0];
MaxT[0] = T[0];
for (int i = 1; i < N; i++) {
P[i] = min(P[i - 1], T[i]);
MaxT[i] = max(MaxT[i - 1], T[i]);
}
build_sparse_table();
global_reach.assign(M, -1);
// Precalculate full-bound reachability for rapid O(1) query matching
for (int S = 0; S < M; S++) {
if (global_reach[S] != -1) continue;
int curr = S;
int curr_h = H_val[S];
while (true) {
int T_curr = get_F(curr_h);
int l = get_left(curr, T_curr, 0);
int r = get_right(curr, T_curr, M - 1);
int nxt = query_min_idx(l, r);
if (nxt == curr || global_reach[nxt] != -1) {
global_reach[S] = (nxt == curr) ? T_curr : global_reach[nxt];
break;
}
curr = nxt;
curr_h = H_val[curr];
}
}
}
bool can_reach(int L, int R, int S, int D) {
int req = query_max(min(S, D), max(S, D));
if (L == 0 && R == M - 1) {
return global_reach[S] > req && global_reach[D] > req;
}
int reach_S = simulate(S, L, R, req);
if (reach_S <= req) return false;
int reach_D = simulate(D, L, R, req);
return reach_D > req;
}
