#include "obstacles.h" #include <bits/stdc++.h> using namespace std; using vi = vector<int>; using pi = pair<int, int>; struct SegTree { int n; vi arr; vector<pi> st; SegTree() {} SegTree(int N, vi &Arr) { n = N; arr = Arr; st.assign(4*n, {-1, -1}); build(0, 0, n); } pi combine(pi x, pi y) { pi r = {-1, -1}; if (x.first < 0) r.first = y.first; else if (y.first < 0) r.first = x.first; else r.first = arr[x.first] < arr[y.first] ? x.first : y.first; if (x.second < 0) r.second = y.second; else if (y.second < 0) r.second = x.second; else r.second = arr[x.second] > arr[y.second] ? x.second : y.second; return r; } pi build(int i, int l, int r) { if (l+1==r) return st[i] = {l, l}; int m = l + (r- l)/2; return st[i] = combine(build(2*i+1, l, m), build(2*i+2, m, r)); } pi update(int i, int l, int r, int k, int v) { if (!(l <= k && k < r)) return st[i]; if (l+1==r) {arr[k] = v; return st[i] = {l, l};} int m = l + (r- l)/2; return st[i] = combine(update(2*i+1, l, m, k, v), update(2*i+2, m, r, k, v)); } pi query(int i, int l, int r, int ql, int qr) { if (qr <= l || r <= ql) return {-1, -1}; if (ql <= l && r <= qr) return st[i]; int m = l + (r - l) / 2; return combine(query(2*i+1, l, m, ql, qr), query(2*i+2, m, r, ql, qr)); } // max i in [l, r] such that max([l, i]) < T or min([l, i]) > T int right(int i, int l, int r, int ql, int qr, int T, bool mx) { if (r <= ql || qr <= l) return -1; if (ql <= l && r <= qr) { if ((mx && (st[i].second >= 0 && arr[st[i].second] < T)) || (!mx && (st[i].first >= 0 && arr[st[i].first] > T))) return -1; } if (l + 1 == r) return ((mx && arr[l] >= T) || (!mx && arr[l] <= T)) ? l : -1; int m = l + (r - l) / 2; int left = right(2*i+1, l, m, ql, qr, T, mx); if (left != -1) return left; return right(2*i+2, m, r, ql, qr, T, mx); } // min i in [l, r] such that max([i, r]) < T or min([i, r]) > T int left(int i, int l, int r, int ql, int qr, int T, bool mx) { if (r <= ql || qr <= l) return -1; if (ql <= l && r <= qr) { if ((mx && (st[i].second >= 0 && arr[st[i].second] < T)) || (!mx && (st[i].first >= 0 && arr[st[i].first] > T))) return -1; } if (l + 1 == r) return ((mx && arr[l] >= T) || (!mx && arr[l] <= T)) ? l : -1; int m = l + (r - l) / 2; int right = left(2*i+2, m, r, ql, qr, T, mx); if (right != -1) return right; return left(2*i+1, l, m, ql, qr, T, mx); } }; const int maxlog = 20; struct DSU { int n, timer = 0; vi par, L, R, sz; vector<vector<int>> adj, up; vector<int> tin, tout; DSU(int N = 0) { n = N; adj.resize(2*n); up.assign(2*n, vector<int>(maxlog)); tin.assign(2*n,-1); tout.assign(2*n, -1); sz.assign(2*n, 1); for (int i = 0; i < 2*n; i++) par.push_back(i), L.push_back(i < n ? i : 3*n), R.push_back(i < n ? i : -1); } int find(int v) {return par[v] == v ? v : par[v] = find(par[v]);} void unite(int a, int b) { a = find(a); b = find(b); if (a != b) { adj[n].push_back(a); adj[a].push_back(n); adj[n].push_back(b); adj[b].push_back(n); L[n] = min(L[a], L[b]); R[n] = max(R[a], R[b]); par[a] = par[b] = n++; } } void dfs(int u, int p) { up[u][0] = p; for (int i = 1; i < maxlog; i++) { up[u][i] = up[up[u][i-1]][i-1]; } tin[u] = timer++; for (auto v : adj[u]) { if (v == p) continue; dfs(v, u); } tout[u] = timer; } void process() { for (int i = 0; i < n; i++) { if (tin[find(i)] != -1) continue; dfs(find(i), find(i)); } } bool is_ancestor(int u, int v) { return tin[u] <= tin[v] && tout[u] >= tout[v]; } int lca(int u, int v) { if (is_ancestor(u, v)) return u; if (is_ancestor(v, u)) return v; for (int i = maxlog-1; i >= 0; i--) { if (!is_ancestor(up[u][i], v)) u = up[u][i]; } return up[u][0]; } }; int r, c; SegTree row, col; vi t, h, depth, L, R; DSU dsu; vector<bool> finished; pi get_range(int i, int ca, int cb) { int a = col.left(0, 0, c, 0, ca+1, t[i], true), b = col.right(0, 0, c, cb, c, t[i], true); a = (a == -1) ? 0 : a+1; b = (b == -1) ? c-1 : b-1; return make_pair(a, b); }; void compute(int i, int maxdepth) { if (t[0] <= h[i]) return; if (depth[i] != -1 && (finished[i] || depth[i] >= maxdepth)) return; if (depth[i] == -1) depth[i] = 0; while (depth[i] < maxdepth && depth[i] < r-1) { int mn = col.query(0, 0, c, L[i], R[i]+1).first; int posx = row.right(0, 0, r, depth[i], r, h[mn], false); if (posx == -1) posx = r-1; if (depth[i] >= r-1 || posx == depth[i]) finished[i] = true; if (posx == depth[i]) break; depth[i] = posx; int maxy = row.query(0, 0, r, 0, posx+1).second; auto range = get_range(maxy, L[i], R[i]); L[i] = range.first, R[i] = range.second; } } void initialize(vi T, vi H) { r = T.size(); c = H.size(); t = T; h = H; dsu = DSU(c); depth.assign(c, -1); L.assign(c, 0); R.assign(c, 0); for (int i = 0; i < c; i++) L[i] = R[i] = i; finished.assign(c, false); dsu = DSU(c); row = SegTree(r, T); col = SegTree(c, H); auto depthst = SegTree(c, depth); vector<int> idx(c); iota(idx.begin(), idx.end(), 0); sort(idx.begin(), idx.end(), [&](int i, int j) {return h[i] < h[j];}); for (int ix = 0; ix < c; ix++) { int i = idx[ix]; depth[i] = row.right(0, 0, r, 0, r, h[i], false); if (depth[i] == -1) depth[i] = r-1; int maxy = row.query(0, 0, r, 0, depth[i]+1).second; auto range = get_range(maxy, L[i], R[i]); int x = depthst.right(0, 0, c, i, range.second+1, depth[i], true); int y = depthst.left(0, 0, c, range.first, i+1, depth[i], false); if (x != -1) dsu.unite(i, x); else if (y != -1) dsu.unite(i, y); depth[i] = max(depth[i], x == -1 ? (y == -1 ? -1 : depth[y]) : depth[x]); depthst.update(0, 0, c, i, depth[i]); } dsu.process(); } bool can_reach(int lower, int upper, int s, int d) { if (s>d) swap(s, d); return dsu.find(s) == dsu.find(d) && dsu.L[dsu.lca(s, d)] >= lower && dsu.R[dsu.lca(s, d)] <= upper; // int mx = h[col.query(0, 0, c, s, d+1).second]; // int first = row.right(0, 0, r, 0, r, mx+1, true); // if (first >= r || t[first] <= mx) return false; // return depth[s] >= first && depth[d] >= first; }