#include <bits/stdc++.h>
using namespace std;
static const int LOG = 20;
int N, M;
vector<int> T, H;
vector<int> L, R;
vector<int> parent;
int up[LOG][200005];
/* --- Step 1: Initialize --- */
void initialize(vector<int> _T, vector<int> _H) {
T = _T;
H = _H;
N = T.size();
M = H.size();
vector<int> ord(M);
iota(ord.begin(), ord.end(), 0);
sort(ord.begin(), ord.end(), [&](int a, int b) {
return H[a] < H[b];
});
L.assign(N, M);
R.assign(N, -1);
/* Each row interval */
for (int i = 0; i < N; i++) {
int pos = lower_bound(
ord.begin(),
ord.end(),
T[i],
[&](int idx, int val) {
return H[idx] < val;
}
) - ord.begin();
if (pos == 0) continue;
for (int j = 0; j < pos; j++) {
L[i] = min(L[i], ord[j]);
R[i] = max(R[i], ord[j]);
}
}
/* --- Step 2: Build containment tree --- */
parent.assign(N, -1);
vector<int> stk;
vector<int> rows(N);
iota(rows.begin(), rows.end(), 0);
sort(rows.begin(), rows.end(), [&](int a, int b) {
if (L[a] != L[b]) return L[a] < L[b];
return R[a] > R[b];
});
for (int i : rows) {
while (!stk.empty() &&
!(L[stk.back()] <= L[i] && R[i] <= R[stk.back()])) {
stk.pop_back();
}
parent[i] = stk.empty() ? -1 : stk.back();
stk.push_back(i);
}
/* --- Step 3: Binary lifting --- */
for (int i = 0; i < N; i++)
up[0][i] = parent[i];
for (int k = 1; k < LOG; k++) {
for (int i = 0; i < N; i++) {
int p = up[k - 1][i];
up[k][i] = (p == -1 ? -1 : up[k - 1][p]);
}
}
}
/* climb up while interval stays inside [ql, qr] */
int climb(int v, int ql, int qr) {
for (int k = LOG - 1; k >= 0; k--) {
int p = up[k][v];
if (p != -1 &&
L[p] >= ql &&
R[p] <= qr) {
v = p;
}
}
return v;
}
/* --- Step 4: Queries --- */
bool can_reach(int ql, int qr, int S, int D) {
int a = -1, b = -1;
for (int i = 0; i < N; i++) {
if (L[i] <= S && S <= R[i] &&
L[i] >= ql && R[i] <= qr) {
a = i; break;
}
}
for (int i = 0; i < N; i++) {
if (L[i] <= D && D <= R[i] &&
L[i] >= ql && R[i] <= qr) {
b = i; break;
}
}
if (a == -1 || b == -1) return false;
a = climb(a, ql, qr);
b = climb(b, ql, qr);
if (a == b) return true;
/* check intersection */
return max(L[a], L[b]) <= min(R[a], R[b]);
}
