#include <vector> #include <algorithm> #include <set> #include <cmath> using namespace std; vector<int> T, H; int N, M; vector<int> pref_min, pref_max; vector<int> depth; vector<vector<int>> st; vector<int> log2_; vector<int> parent; vector<int> sz; int find(int x) { if (parent[x] != x) parent[x] = find(parent[x]); return parent[x]; } void unite(int a, int b) { a = find(a); b = find(b); if (a == b) return; if (sz[a] < sz[b]) swap(a, b); parent[b] = a; sz[a] += sz[b]; } void init_sparse() { log2_.resize(M + 1); for (int i = 2; i <= M; ++i) log2_[i] = log2_[i / 2] + 1; int K = log2_[M] + 1; st.assign(K, vector<int>(M)); for (int i = 0; i < M; ++i) st[0][i] = H[i]; for (int k = 1; k < K; ++k) { int len = 1 << k; for (int i = 0; i + len <= M; ++i) { st[k][i] = max(st[k - 1][i], st[k - 1][i + (1 << (k - 1))]); } } } int get_max(int l, int r) { int k = log2_[r - l + 1]; return max(st[k][l], st[k][r - (1 << k) + 1]); } void initialize(vector<int> _T, vector<int> _H) { T = _T; H = _H; N = T.size(); M = H.size(); // prefix min and max of T pref_min.resize(N); pref_max.resize(N); pref_min[0] = pref_max[0] = T[0]; for (int i = 1; i < N; ++i) { pref_min[i] = min(pref_min[i - 1], T[i]); pref_max[i] = max(pref_max[i - 1], T[i]); } // depth[j] = first row where prefix_min <= H[j] (or N) depth.assign(M, N); vector<pair<int, int>> cols(M); for (int j = 0; j < M; ++j) cols[j] = {H[j], j}; sort(cols.begin(), cols.end(), greater<pair<int, int>>()); // descending by H int ptr = 0; for (int i = 0; i < N; ++i) { int cur_min = pref_min[i]; while (ptr < M && cols[ptr].first >= cur_min) { depth[cols[ptr].second] = i; ++ptr; } } // range maximum queries on H init_sparse(); // DSU initialization parent.resize(M); sz.assign(M, 1); for (int i = 0; i < M; ++i) parent[i] = i; // process only columns that are free on row 0 (depth > 0) vector<pair<int, int>> good; // (key, index) for (int j = 0; j < M; ++j) { if (depth[j] > 0) { int L = depth[j] - 1; int key = pref_max[L]; good.emplace_back(key, j); } } // sort by key descending sort(good.begin(), good.end(), greater<pair<int, int>>()); set<int> active; // set of indices already processed (good columns) for (auto& p : good) { int key = p.first; int idx = p.second; auto it = active.lower_bound(idx); // try to connect with the nearest column on the left if (it != active.begin()) { int left = *prev(it); int mx = get_max(left, idx); if (mx < key) unite(idx, left); } // try to connect with the nearest column on the right if (it != active.end()) { int right = *it; int mx = get_max(idx, right); if (mx < key) unite(idx, right); } active.insert(idx); } } bool can_reach(int L, int R, int S, int D) { // constraints guarantee L = 0, R = M-1, so the whole grid is available. return find(S) == find(D); }