#include <vector>
#include <set>
#include <algorithm>
using namespace std;
static int N, M;
static vector<int> T, H;
static vector<int> P, M_T, L;
static vector<int> parent, rnk;
static set<int> active;
static vector<int> seg;
// ---------- DSU ----------
int dsu_find(int x) {
while (parent[x] != x) {
parent[x] = parent[parent[x]];
x = parent[x];
}
return x;
}
void dsu_union(int a, int b) {
a = dsu_find(a);
b = dsu_find(b);
if (a == b) return;
if (rnk[a] < rnk[b]) swap(a, b);
parent[b] = a;
rnk[a] += rnk[b];
}
// -------------------------
// ---------- Segment tree (max) ----------
void build(int node, int l, int r) {
if (l == r) {
seg[node] = H[l];
return;
}
int mid = (l + r) / 2;
build(node * 2, l, mid);
build(node * 2 + 1, mid + 1, r);
seg[node] = max(seg[node * 2], seg[node * 2 + 1]);
}
// leftmost index in [ql, qr] with value >= X, or -1
int query_first(int node, int l, int r, int ql, int qr, int X) {
if (r < ql || l > qr || seg[node] < X) return -1;
if (l == r) return l;
int mid = (l + r) / 2;
int left_res = query_first(node * 2, l, mid, ql, qr, X);
if (left_res != -1) return left_res;
return query_first(node * 2 + 1, mid + 1, r, ql, qr, X);
}
// rightmost index in [ql, qr] with value >= X, or -1
int query_last(int node, int l, int r, int ql, int qr, int X) {
if (r < ql || l > qr || seg[node] < X) return -1;
if (l == r) return l;
int mid = (l + r) / 2;
int right_res = query_last(node * 2 + 1, mid + 1, r, ql, qr, X);
if (right_res != -1) return right_res;
return query_last(node * 2, l, mid, ql, qr, X);
}
// ----------------------------------------
void initialize(vector<int> T_, vector<int> H_) {
T = move(T_);
H = move(H_);
N = T.size();
M = H.size();
// prefix minimum P
P.resize(N);
P[0] = T[0];
for (int i = 1; i < N; ++i) P[i] = min(P[i-1], T[i]);
// prefix maximum of T
M_T.resize(N);
M_T[0] = T[0];
for (int i = 1; i < N; ++i) M_T[i] = max(M_T[i-1], T[i]);
// L[j] for each column
L.resize(M);
for (int j = 0; j < M; ++j) {
int val = H[j];
int lo = 0, hi = N; // hi == N means not found
while (lo < hi) {
int mid = (lo + hi) / 2;
if (P[mid] <= val) hi = mid;
else lo = mid + 1;
}
if (lo == N) L[j] = N; // always accessible
else L[j] = lo;
}
// build segment tree on H
seg.resize(4 * M);
build(1, 0, M - 1);
// group columns by L (only L > 0, because L=0 cannot be reached from top)
vector<vector<int>> cols_by_L(N + 1);
for (int j = 0; j < M; ++j) {
if (L[j] > 0) cols_by_L[L[j]].push_back(j);
}
// DSU init
parent.resize(M);
rnk.assign(M, 1);
for (int i = 0; i < M; ++i) parent[i] = i;
// process in decreasing L
active.clear();
for (int l = N; l >= 1; --l) {
int X = M_T[l - 1];
for (int j : cols_by_L[l]) {
// if H[j] >= X, this column can never be connected via threshold X
if (H[j] < X) {
// left boundary of the interval where H < X containing j
int left_bound = 0;
if (j > 0) {
int p = query_last(1, 0, M - 1, 0, j - 1, X);
if (p != -1) left_bound = p + 1;
}
// right boundary
int right_bound = M - 1;
if (j < M - 1) {
int q = query_first(1, 0, M - 1, j + 1, M - 1, X);
if (q != -1) right_bound = q - 1;
}
// look for an already active column inside that interval
auto it = active.lower_bound(left_bound);
if (it != active.end() && *it <= right_bound) {
dsu_union(j, *it);
}
}
active.insert(j);
}
}
}
bool can_reach(int L_, int R, int S, int D) {
// according to the subproblem constraints, L = 0 and R = M-1 for all queries.
// therefore the answer depends only on whether S and D are in the same connected component.
return dsu_find(S) == dsu_find(D);
}
