#include "obstacles.h" #include <bits/stdc++.h> using namespace std; const int N = 4e5 + 10; const int LOG = 21; vector<int>T, H; int n, m; struct sparse_table { vector<int>a; int sp_mx[N][LOG]; int sp_mn[N][LOG]; int id_mn[N][LOG]; int id_mx[N][LOG]; void build_sparse(vector<int>H) { int m_ = H.size(); a = H; for (int i = 0; i < m_; i++) { sp_mn[i][0] = H[i]; sp_mx[i][0] = H[i]; id_mn[i][0] = i; id_mx[i][0] = i; } for (int j = 1; j < LOG; j++) { for (int i = 0; i + (1 << j) <= m_; i++) { int mid = i + (1 << (j - 1)); if (sp_mx[i][j - 1] >= sp_mx[mid][j - 1]) { sp_mx[i][j] = sp_mx[i][j - 1]; id_mx[i][j] = id_mx[i][j - 1]; } else { sp_mx[i][j] = sp_mx[mid][j - 1]; id_mx[i][j] = id_mx[mid][j - 1]; } if (sp_mn[i][j - 1] <= sp_mn[mid][j - 1]) { sp_mn[i][j] = sp_mn[i][j - 1]; id_mn[i][j] = id_mn[i][j - 1]; } else { sp_mn[i][j] = sp_mn[mid][j - 1]; id_mn[i][j] = id_mn[mid][j - 1]; } } } } int query_mx(int l, int r) { int lg = log2(r - l + 1); return max(sp_mx[l][lg], sp_mx[r - (1 << lg) + 1][lg]); } int query_mn(int l, int r) { int lg = log2(r - l + 1); return min(sp_mn[l][lg], sp_mn[r - (1 << lg) + 1][lg]); } int query_id_mx(int l, int r) { int lg = log2(r - l + 1); int a = sp_mx[l][lg], b = sp_mx[r - (1 << lg) + 1][lg]; if (a >= b) return id_mx[l][lg]; return id_mx[r - (1 << lg) + 1][lg]; } int query_id_mn(int l, int r) { int lg = log2(r - l + 1); int a = sp_mn[l][lg], b = sp_mn[r - (1 << lg) + 1][lg]; if (a <= b) return id_mn[l][lg]; return id_mn[r - (1 << lg) + 1][lg]; } }c_sp, r_sp; bool is_free(int i, int j) { return T[i] > H[j]; } int l[N], r[N], right_most_x[N], left_most_x[N], t[N], mn_ind[N]; pair<int, int>find_lr(int ind, int S) { int ansl = S, ansr = S; int L = 0, R = S; while (L <= R && L >= 0 && R < m) { int mid = (L + R) / 2; if (r_sp.query_mx(mid, S) < T[ind]) { ansl = mid; R = mid - 1; } else { L = mid + 1; } } L = S, R = m - 1; while (L <= R && L >= 0 && R < m) { int mid = (L + R) / 2; if (r_sp.query_mx(S, mid) < T[ind]) { ansr = mid; L = mid + 1; } else { R = mid - 1; } } return { ansl, ansr }; } int nxt[N]; struct node { int ind, t; bool operator<(node const& o) const { if (ind != o.ind) return ind < o.ind; return t < o.t; } }; map<pair<int, int>, int>mp; struct dsu_ { int p[N], sz[N]; int n; void init(int _n) { n = _n; for (int i = 1; i <= n; i++) p[i] = i, sz[i] = 1; } int find(int a) { if (a != p[a]) return p[a] = find(p[a]); return p[a]; } void merge(int a, int b) { a = find(a), b = find(b); if (a == b)return; if (sz[a] < sz[b])swap(a, b); sz[a] += sz[b]; sz[b] = 0; p[b] = a; } bool ask(int a, int b) { a = find(a); b = find(b); return (a == b); } }dsu; void initialize(std::vector<int> T, std::vector<int> H) { n = T.size(); m = H.size(); ::T = T; ::H = H; r_sp.build_sparse(H); c_sp.build_sparse(T); int cnt = 0; queue<int>cur; for (int i = 0; i < m;) { if (is_free(0, i)) { cnt++; cur.push(cnt); pair<int, int>P = find_lr(0, i); l[cnt] = P.first; r[cnt] = P.second; i = r[cnt] + 2; t[cnt] = 0; mp[{0, r_sp.query_id_mn(l[cnt], r[cnt])}] = cnt; } else i++; } while (!cur.empty()) { int i = cur.front(); cur.pop(); int ind = r_sp.query_id_mn(l[i], r[i]); int x = t[i] + 1; while (x < n) { if (c_sp.query_id_mn(t[i], x) <= H[ind]) break; pair<int, int>P = find_lr(x, ind); if (P.first <= l[i] && P.second >= r[i]) { if (P.first < l[i] || P.second > r[i]) { pair<int, int> key = { x, r_sp.query_id_mn(P.first, P.second) }; if (mp.count(key)) { nxt[i] = mp[key]; } else { cnt++; l[cnt] = P.first; r[cnt] = P.second; t[cnt] = x; mp[key] = cnt; cur.push(cnt); nxt[i] = cnt; } break; } } x++; } } dsu.init(cnt + 10); for (int i = 1; i < cnt; i++) if (nxt[i]) dsu.merge(i, nxt[i]); } bool can_reach(int L, int R, int S, int D) { if (S > D) swap(S, D); pair<int, int>p1 = find_lr(0, S); pair<int, int>p2 = find_lr(0, D); int cnt1 = mp[{0, r_sp.query_id_mn(p1.first, p1.second)}]; int cnt2 = mp[{0, r_sp.query_id_mn(p2.first, p2.second)}]; return dsu.ask(cnt1, cnt2); }