#include "obstacles.h" #include <bits/stdc++.h> using namespace std; class DSU { vector<int> parent, size; public: int sets; DSU(int N = 0) { init(N); } void init(int N){ this->parent.resize(N); this->size.resize(N, 1); for(int i = 0; i < N; i++) this->parent[i] = i; this->sets = N; } int find(int x) { if(this->parent[x] != x) { this->parent[x] = find(this->parent[x]); } return this->parent[x]; } void unite(int x, int y) { int a = find(x); int b = find(y); if (a != b) { if (this->size[a] < this->size[b]) swap(a, b); this->parent[b] = a; this->size[a] += this->size[b]; } } int get_size(int x) { return this->size[find(x)]; } void clear() { int N = this->parent.size(); for (int i = 0; i < N; i++) { this->parent[i] = i; this->size[i] = 1; } this->sets = N; } }; template <typename T, T (*op)(T, T)> struct SparseTable { int N, LOG; vector<vector<T>> st; void build(const vector<T> &v) { N = v.size(); LOG = 32 - __builtin_clz(N); st.assign(LOG, vector<T>(N)); st[0] = v; for (int k = 1; k < LOG; k++) { int len = 1 << k; int half = len >> 1; for (int i = 0; i + len <= N; i++) { st[k][i] = op(st[k-1][i], st[k-1][i+half]); } } } T query(int l, int r) const { --r; int len = r - l + 1; int k = 31 - __builtin_clz(len); return op(st[k][l], st[k][r - (1<<k) + 1]); } }; int dx[4] = {-1,0,1,0}; int dy[4] = {0,-1,0,1}; vector<int> T,H; vector<int> down,lt,rt,downmx; int n,m; DSU dsu; int maxf (int x,int y){ return max(x,y); }; struct Node { int idx; int val; }; Node nmaxf (Node x, Node y){ Node z; if(x.val < y.val) swap(x,y); z.val = x.val; z.idx = x.idx; return z; } void initialize(vector<int> t, vector<int> h) { n = t.size(); m = h.size(); T=t; H=h; dsu.init(m); downmx.resize(m,0); down.resize(m,0); lt.resize(m,0); rt.resize(m,0); static const int INF = 1e9+1; vector<int> st1(n); st1[0] = T[0]; for (int i = 1; i < n; ++i) st1[i] = min(st1[i-1], T[i]); SparseTable<int,maxf> st2; st2.build(h); vector<Node> ret(n); for(int i = 0; i < n; ++i){ Node qe; qe.idx = i; qe.val = T[i]; ret[i] = qe; } Node def; def.idx = 0; def.val = 0; // SegTree<Node> st3 = SegTree<Node>(n,def,[&],ret); SparseTable<Node,nmaxf> st3; st3.build(ret); for(int i = 0; i < m; ++i) { if(t[0] <= h[i]){ down[i] = -1; }else{ int l = 1, r = n; int ans = 0; while (l <= r) { int md = (l + r) >> 1; if (st1[md-1] > H[i]) { ans = md; l = md+1; } else { r = md-1; } } down[i] = ans-1; downmx[i] = (st3.query(0,ans)).idx; } } for(int i = 0; i < m; ++i){ if(down[i]==-1)continue; int l = i, r = m; int ans = i; while (l <= r) { int md = (l + r) >> 1; if (st2.query(i, md) < T[downmx[i]]) { ans = md; l = md+1; } else { r = md-1; } } rt[i] = ans-1; } for(int i = 0; i < m; ++i){ if(down[i]==-1)continue; int l = 0, r = i; int ans = i+1; while (l <= r) { int md = (l + r) >> 1; if (st2.query(md, i+1) < T[downmx[i]]) { ans = md; r = md-1; } else { l = md+1; } } lt[i] = ans; } for(int i = 0; i + 1< m; ++i){ if(down[i] >= 0 and down[i+1] >=0){ dsu.unite(i,i+1); } } // SegTree<int> dst(m,0,[&](auto x, auto y){ // return max(x,y); // },down); SparseTable<int,maxf> dst; dst.build(down); for(int i = 0; i < m; ++i){ if(down[i] == -1) continue; int curr = downmx[i]; int idx = i; int l = i+1, r = rt[i]; int ans = i; while (l <= r) { int md = (l + r) >> 1; if (dst.query(i+1, md+1) >= curr) { ans = md; r = md-1; } else { l = md+1; } } if(ans != i){ dsu.unite(ans,i); } } for(int i = 0; i < m; ++i){ if(down[i] == -1) continue; int curr = downmx[i]; int idx = i; int l = lt[i], r = i-1; int ans = i; while (l <= r) { int md = (l + r) >> 1; if (dst.query(md, i) >= curr) { ans = md; l = md+1; } else { r = md-1; } } if(ans != i){ dsu.unite(ans,i); } } } bool can_reach(int L, int R, int S, int D) { int r1 = dsu.find(S); int r2 = dsu.find(D); return (r1==r2); }