#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;
// RMQ：查询区间内必须跨越的最大势垒 (Max Barrier)
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]);
}
// RMQ：查询区间内湿度最低的列索引 (Min Humidity Index)
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;
}
// 核心：基于当前持有的最小湿度h，羊驼能深入到的最大温度
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];
}
// 全局边界控制与 Kruskal 重构树
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;
// 计算相邻列之间的墙壁(Barrier)
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表 初始化: 湿度最小值索引
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 = max(0, prv[i]);
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;
// 单向覆盖检验 Lambda 闭包
auto check = [&](int X, int Y) {
if (X == Y) return true;
int rt = rts[X];
int u = X;
// 步骤1：O(logM) 跳至被限制条件允许的最大原生重构辖区(KRT Node)
for (int k = LOG - 1; k >= 0; k--) {
int p = up_KRT[u][k];
if (depth_KRT[p] >= depth_KRT[rt] && l_bound[p] >= L && r_bound[p] <= R) u = p;
}
// 步骤2：目标是否已被囊括在可轻易漫游的辖区中
if (Y >= l_bound[u] && Y <= r_bound[u]) return true;
// 步骤3：目标在辖区外，需贪心进行单项扩张突破
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);
}
