#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, ansr; int l = 0, r = S; while (l <= r && l >= 0 && r < m) { int mid = (l + r) / 2l; 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) { int mid = (l + r) / 2l; 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<node, 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]; return p[a] = find(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]; p[b] = a; } bool ask(int a, int b) { a = find(a); b = find(b); if (a == b)return true; else return false; } }dsu; void initialize(std::vector<int> T, std::vector<int> H) { n = T.size(); m = H.size(); (::T).resize(n); (::H).resize(m); for (int i = 0; i < n; i++)(::T)[i] = T[i]; for (int i = 0; i < m; i++)(::H)[i] = H[i]; 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]; bool bol = true; while (x < n) { if (!bol)break; x++; if (c_sp.query_id_mn(t[i], x) <= H[ind]) break; pair<int, int>P; P = find_lr(x, ind); if (P.first < l[i] || P.second > r[i]) { if (mp[{x, r_sp.query_id_mn(P.first, P.second)}]) { nxt[i] = cnt; break; } cnt++; l[cnt] = P.first; r[cnt] = P.second; t[cnt] = x; mp[{x, r_sp.query_id_mn(P.first, P.second)}] = cnt; cur.push(cnt); nxt[i] = cnt; break; } } } 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)}]; if (dsu.ask(cnt1, cnt2))return true; else return false; }