#include <vector>
#include <algorithm>
#include <numeric>
using namespace std;
static int N, M;
static vector<int> root_node;
void initialize(std::vector<int> T, std::vector<int> H) {
N = T.size();
M = H.size();
// 预处理前缀最小值和最大值
vector<int> PT(N);
PT[0] = T[0];
for(int i = 1; i < N; i++) PT[i] = min(PT[i-1], T[i]);
vector<int> MT(N);
MT[0] = T[0];
for(int i = 1; i < N; i++) MT[i] = max(MT[i-1], T[i]);
// F(h): 给定最小湿度h，从第0行出发只能走温度>h的行，所能探测到的最大温度
auto F = [&](int h) {
int low = 0, high = N - 1, best = -1;
while(low <= high) {
int mid = low + (high - low) / 2;
if(PT[mid] > h) {
best = mid;
low = mid + 1;
} else {
high = mid - 1;
}
}
if(best == -1) return 0;
return MT[best];
};
if (M == 1) {
root_node.assign(1, 0);
return;
}
struct Edge {
int u, v, w;
bool operator<(const Edge& o) const {
return w < o.w;
}
};
vector<Edge> edges;
edges.reserve(M - 1);
for(int i = 0; i < M - 1; i++) {
edges.push_back({i, i + 1, max(H[i], H[i+1])});
}
sort(edges.begin(), edges.end());
// 并查集建立 Kruskal 重构树
vector<int> dsu(2 * M - 1);
iota(dsu.begin(), dsu.end(), 0);
auto find_set = [&](auto& self, int i) -> int {
return dsu[i] == i ? i : dsu[i] = self(self, dsu[i]);
};
vector<int> parent_node(2 * M - 1, -1);
vector<int> val(2 * M - 1, 0);
vector<int> min_H(2 * M - 1, 0);
for(int i = 0; i < M; i++) min_H[i] = H[i];
int nxt = M;
for(auto& e : edges) {
int u = find_set(find_set, e.u);
int v = find_set(find_set, e.v);
if(u != v) {
parent_node[u] = nxt;
parent_node[v] = nxt;
val[nxt] = e.w;
min_H[nxt] = min(min_H[u], min_H[v]);
dsu[u] = nxt;
dsu[v] = nxt;
nxt++;
}
}
// 判断每个节点是否能够往上突破进入父节点
vector<bool> can_up(2 * M - 1, false);
for(int i = 0; i < 2 * M - 1; i++) {
if(parent_node[i] != -1) {
int p = parent_node[i];
if(F(min_H[i]) > val[p]) {
can_up[i] = true;
}
}
}
// 预计算出每个节点的最终归属（它能达到的最顶层的重构树节点）
root_node.assign(2 * M - 1, 0);
root_node[2 * M - 2] = 2 * M - 2;
for(int i = 2 * M - 3; i >= 0; i--) {
if(can_up[i]) {
root_node[i] = root_node[parent_node[i]];
} else {
root_node[i] = i; // 无法突破，被限制在当前连通块中
}
}
}
bool can_reach(int L, int R, int S, int D) {
// 如果两点收敛（往上溯源）停在同一个最大的相通父区块内，说明连通
return root_node[S] == root_node[D];
}
