#include <vector>
#include <algorithm>
using namespace std;
const int LOG = 20;
static int n, m;
static vector<int> T_val, H_val;
static vector<int> pt, mt;
static vector<int> W;
static vector<vector<int>> st_W;
static vector<vector<int>> st_H;
static int query_W(int l, int r) {
if (l > r) return -1;
int k = 31 - __builtin_clz(r - l + 1);
return max(st_W[k][l], st_W[k][r - (1 << k) + 1]);
}
static int query_H_idx(int l, int r) {
if (l > r) return -1;
int k = 31 - __builtin_clz(r - l + 1);
int idx1 = st_H[k][l];
int idx2 = st_H[k][r - (1 << k) + 1];
return H_val[idx1] <= H_val[idx2] ? idx1 : idx2;
}
static int calc(int h) {
int L = 0, R = n - 1, p = -1;
while (L <= R) {
int mid = L + (R - L) / 2;
if (pt[mid] > h) {
p = mid;
L = mid + 1;
} else {
R = mid - 1;
}
}
if (p == -1) return 0;
return mt[p];
}
// 约束边界与倍增结构
static vector<int> fa, l_bound, r_bound, rts;
static vector<vector<int>> up_KRT;
static vector<int> depth_KRT;
static vector<int> nxt;
static vector<vector<int>> up_R;
static vector<vector<bool>> fail_R;
static vector<int> prv;
static vector<vector<int>> up_L;
static vector<vector<bool>> fail_L;
void initialize(vector<int> T, vector<int> H) {
n = T.size(); m = H.size();
T_val = T; H_val = H;
pt.assign(n, 0); mt.assign(n, 0);
pt[0] = T[0]; mt[0] = T[0];
for (int i = 1; i < n; i++) {
pt[i] = min(pt[i - 1], T[i]);
mt[i] = max(mt[i - 1], T[i]);
}
if (m == 1) return;
W.assign(m - 1, 0);
for (int i = 0; i < m - 1; i++) W[i] = max(H[i], H[i + 1]);
// ST表 初始化
st_W.assign(LOG, vector<int>(m, 0));
for (int i = 0; i < m - 1; i++) st_W[0][i] = W[i];
for (int k = 1; k < LOG; k++) {
for (int i = 0; i + (1 << k) <= m - 1; i++) {
st_W[k][i] = max(st_W[k - 1][i], st_W[k - 1][i + (1 << (k - 1))]);
}
}
st_H.assign(LOG, vector<int>(m, 0));
for (int i = 0; i < m; i++) st_H[0][i] = i;
for (int k = 1; k < LOG; k++) {
for (int i = 0; i + (1 << k) <= m; i++) {
int idx1 = st_H[k - 1][i];
int idx2 = st_H[k - 1][i + (1 << (k - 1))];
st_H[k][i] = H[idx1] <= H[idx2] ? idx1 : idx2;
}
}
// Kruskal重构树 (KRT) 初始化
struct Edge { int u, v, w; bool operator<(const Edge& rhs) const { return w < rhs.w; } };
vector<Edge> edges;
edges.reserve(m - 1);
for (int i = 0; i < m - 1; i++) edges.push_back({i, i + 1, W[i]});
sort(edges.begin(), edges.end());
vector<int> p(2 * m - 1);
for (int i = 0; i < 2 * m - 1; i++) p[i] = i;
auto find_set = [&](auto& self, int x) -> int { return x == p[x] ? x : p[x] = self(self, p[x]); };
fa.assign(2 * m - 1, -1);
l_bound.assign(2 * m - 1, 0); r_bound.assign(2 * m - 1, 0);
vector<int> mn_H(2 * m - 1, 0), val(2 * m - 1, 0);
for(int i = 0; i < m; i++) { mn_H[i] = H[i]; l_bound[i] = i; r_bound[i] = i; }
int nxt_node = m;
for (auto e : edges) {
int u = find_set(find_set, e.u), v = find_set(find_set, e.v);
if (u != v) {
fa[u] = fa[v] = nxt_node;
l_bound[nxt_node] = min(l_bound[u], l_bound[v]);
r_bound[nxt_node] = max(r_bound[u], r_bound[v]);
val[nxt_node] = e.w;
mn_H[nxt_node] = min(mn_H[u], mn_H[v]);
p[u] = p[v] = nxt_node;
nxt_node++;
}
}
vector<bool> flg(2 * m - 1, false);
for (int i = 0; i < 2 * m - 1; i++) {
if (fa[i] != -1 && calc(mn_H[i]) > val[fa[i]]) flg[i] = true;
}
rts.assign(2 * m - 1, 0);
rts[2 * m - 2] = 2 * m - 2;
for (int i = 2 * m - 3; i >= 0; i--) rts[i] = flg[i] ? rts[fa[i]] : i;
up_KRT.assign(2 * m - 1, vector<int>(LOG, -1));
depth_KRT.assign(2 * m - 1, 0);
for (int i = 2 * m - 2; i >= 0; i--) {
if (fa[i] != -1) depth_KRT[i] = depth_KRT[fa[i]] + 1;
up_KRT[i][0] = fa[i] == -1 ? i : fa[i];
}
for (int k = 1; k < LOG; k++) {
for (int i = 0; i < 2 * m - 1; i++) up_KRT[i][k] = up_KRT[up_KRT[i][k - 1]][k - 1];
}
// 单调栈构造：向右扩张跳跃表 (Right Expansion Tree)
nxt.assign(m, m);
vector<int> st;
for (int i = 0; i < m; i++) {
while (!st.empty() && H[st.back()] >= H[i]) { nxt[st.back()] = i; st.pop_back(); }
st.push_back(i);
}
up_R.assign(m + 1, vector<int>(LOG, m));
fail_R.assign(m + 1, vector<bool>(LOG, false));
for (int i = 0; i < m; i++) {
up_R[i][0] = nxt[i];
int r_edge = min(m - 2, nxt[i] - 1);
fail_R[i][0] = (calc(H[i]) <= query_W(i, r_edge));
}
for (int k = 1; k < LOG; k++) {
for (int i = 0; i <= m; i++) {
up_R[i][k] = up_R[up_R[i][k - 1]][k - 1];
fail_R[i][k] = fail_R[i][k - 1] | fail_R[up_R[i][k - 1]][k - 1];
}
}
// 单调栈构造：向左扩张跳跃表 (Left Expansion Tree)
prv.assign(m, -1);
st.clear();
for (int i = m - 1; i >= 0; i--) {
while (!st.empty() && H[st.back()] >= H[i]) { prv[st.back()] = i; st.pop_back(); }
st.push_back(i);
}
up_L.assign(m + 1, vector<int>(LOG, m));
fail_L.assign(m + 1, vector<bool>(LOG, false));
for (int i = 0; i < m; i++) {
up_L[i][0] = prv[i] == -1 ? m : prv[i];
int l_edge = prv[i] + 1;
fail_L[i][0] = (calc(H[i]) <= query_W(l_edge, i - 1));
}
for (int k = 1; k < LOG; k++) {
for (int i = 0; i <= m; i++) {
up_L[i][k] = up_L[up_L[i][k - 1]][k - 1];
fail_L[i][k] = fail_L[i][k - 1] | fail_L[up_L[i][k - 1]][k - 1];
}
}
}
bool can_reach(int L, int R, int S, int D) {
if (m == 1) return true;
// 查询闭包封装（必须使得 S 能够扫向 D，并且 D 也能扫回 S 才能构成可跨越且互通的通道）
auto check = [&](int X, int Y) {
int rt = rts[X];
int u = X;
for (int k = LOG - 1; k >= 0; k--) {
int p = up_KRT[u][k];
// 确保攀爬不逾越该区块被授权的最高级(rt)，且边界不出圈(>=L 且 <=R)
if (depth_KRT[p] >= depth_KRT[rt] && l_bound[p] >= L && r_bound[p] <= R) u = p;
}
// 当无需任何扩荒行为时：目标位置 Y 在可安全徘徊的领域内
if (Y >= l_bound[u] && Y <= r_bound[u]) return true;
if (Y > r_bound[u]) {
// 向右扩张突破
int curr = query_H_idx(l_bound[u], r_bound[u]);
for (int k = LOG - 1; k >= 0; k--) {
if (up_R[curr][k] != m && up_R[curr][k] <= Y && !fail_R[curr][k]) {
curr = up_R[curr][k];
}
}
return calc(H_val[curr]) > query_W(curr, Y - 1);
} else {
// 向左扩张突破
int curr = query_H_idx(l_bound[u], r_bound[u]);
for (int k = LOG - 1; k >= 0; k--) {
if (up_L[curr][k] != m && up_L[curr][k] >= Y && !fail_L[curr][k]) {
curr = up_L[curr][k];
}
}
return calc(H_val[curr]) > query_W(Y, curr - 1);
}
};
// 可达性具备严谨的对称性，必须首尾相接
return check(S, D) && check(D, S);
}
