//#include "obstacles.h" #include <bits/stdc++.h> using namespace std; #define all(x) x.begin(), x.end() #define ll long long #define V vector #define pb push_back #define FASTIO ios::sync_with_stdio(false); cin.tie(nullptr); struct node{ int ind, l, r, t; }; struct edge{ int to, lft, rgt; }; const int N = 200000 + 5; const int M = 16 * N; const int LG = 19; const int LG_C = 23; int n, m; V<int> t, h; int stmn[N][LG], stmx[N][LG]; int tmn[N][LG], tmx[N][LG]; int lg2[N]; int p[M], sz_[M]; V<edge> adj[M]; int up[M][LG_C], upl[M][LG_C], upr[M][LG_C]; bool dad[M]; int dep[M]; int nd[N]; int timer = 1; map<tuple<int,int,int>, int> mp; void crt(int x){ p[x] = x; sz_[x] = 1; dad[x] = true; } int find(int x){ return p[x] == x ? x : p[x] = find(p[x]); } int min_rng(int l, int r){ int j = lg2[r - l + 1]; return min(stmn[l][j], stmn[r - (1 << j) + 1][j]); } int max_rng(int l, int r){ int j = lg2[r - l + 1]; return max(stmx[l][j], stmx[r - (1 << j) + 1][j]); } int mnt_rng(int l, int r){ int j = lg2[r - l + 1]; return min(tmn[l][j], tmn[r - (1 << j) + 1][j]); } int mxt_rng(int l, int r){ int j = lg2[r - l + 1]; return max(tmx[l][j], tmx[r - (1 << j) + 1][j]); } void merge(node x, node y){ dad[x.ind] = false; int mn = mnt_rng(x.t, y.t); int l = x.l, r = x.r - 1, ans = x.r; while (l <= r) { int md = (l + r) >> 1; if (min_rng(md, x.r) < mn) ans = md, r = md - 1; else l = md + 1; } int nl = ans; l = x.l + 1; r = x.r; ans = x.l; while (l <= r) { int md = (l + r) >> 1; if (min_rng(md, x.r) < mn) ans = md, l = md + 1; else r = md - 1; } int nr = ans; adj[y.ind].pb({x.ind, nl, nr}); int a = find(x.ind); int b = find(y.ind); if(a == b) return; if(sz_[a] < sz_[b]) swap(a, b); p[b] = a; sz_[a] += sz_[b]; } void expand(node x){ if(x.l == 1 && x.r == m) return; if(x.t == n) return; int vl = min(h[x.l - 1], h[x.r + 1]); if(mxt_rng(x.t + 1, n) <= vl) return; int l = x.t + 1, r = n - 1, ans = n; while(l <= r){ int md = (l + r) >> 1; if(mxt_rng(x.t + 1, md) <= vl) l = md + 1; else ans = md, r = md - 1; } if(mnt_rng(x.t + 1, ans) <= min_rng(x.l, x.r)) return; int nwt = ans; l = 1; r = x.l - 1; ans = x.l; while(l <= r){ int md = (l + r) >> 1; if(max_rng(md, x.l) < t[nwt]) ans = md, r = md - 1; else l = md + 1; } int nwl = ans; l = x.r + 1; r = m; ans = x.r; while(l <= r){ int md = (l + r) >> 1; if(max_rng(x.r, md) < t[nwt]) ans = md, l = md + 1; else r = md - 1; } int nwr = ans; auto key = make_tuple(nwl, nwr, nwt); if(mp.count(key)){ merge(x, {mp[key], nwl, nwr, nwt}); }else{ mp[key] = timer; crt(timer); merge(x, {timer, nwl, nwr, nwt}); expand({timer, nwl, nwr, nwt}); ++timer; } } void dfs(int v){ for (auto e : adj[v]) { int ch = e.to; dep[ch] = dep[v] + 1; up[ch][0] = v; upl[ch][0] = e.lft; upr[ch][0] = e.rgt; for (int i = 1; i < LG_C; ++i) { up[ch][i] = up[up[ch][i - 1]][i - 1]; upl[ch][i] = max(upl[ch][i - 1], upl[up[ch][i - 1]][i - 1]); upr[ch][i] = min(upr[ch][i - 1], upr[up[ch][i - 1]][i - 1]); } dfs(ch); } } void tr(int root){ for (int i = 0; i < LG_C; ++i) { up[root][i] = root; upl[root][i] = 0; upr[root][i] = m + 1; } dep[root] = 0; dfs(root); } bool is_s(int a, int b, int l, int r){ if (dep[a] < dep[b]) swap(a, b); int d = dep[a] - dep[b]; for (int i = 0; i < LG_C; ++i) if (d & (1 << i)) { if (upl[a][i] > r || upr[a][i] < l) return false; a = up[a][i]; } if (a == b) return true; for (int i = LG_C - 1; i >= 0; --i) { if (up[a][i] != up[b][i]) { if (upl[a][i] > r || upr[a][i] < l) return false; if (upl[b][i] > r || upr[b][i] < l) return false; a = up[a][i]; b = up[b][i]; } } if (upl[a][0] > r || upr[a][0] < l) return false; if (upl[b][0] > r || upr[b][0] < l) return false; return true; } void initialize(V<int> T, V<int> H){ n = T.size(); m = H.size(); t.assign(n + 1, 0); h.assign(m + 2, 1e9 + 7); for(int i = 1; i <= n; i++) t[i] = T[i - 1]; for(int i = 1; i <= m; i++) h[i] = H[i - 1]; lg2[1] = 0; for(int i = 2; i < N; i++) lg2[i] = lg2[i >> 1] + 1; for(int i = 1; i <= m; i++) stmn[i][0] = stmx[i][0] = h[i]; for(int j = 1; j < LG; j++) for(int i = 1; i + (1 << (j - 1)) <= m; i++){ stmn[i][j] = min(stmn[i][j - 1], stmn[i + (1 << (j - 1))][j - 1]); stmx[i][j] = max(stmx[i][j - 1], stmx[i + (1 << (j - 1))][j - 1]); } for(int i = 1; i <= n; i++) tmn[i][0] = tmx[i][0] = t[i]; for(int j = 1; j < LG; j++) for(int i = 1; i + (1 << (j - 1)) <= n; i++){ tmn[i][j] = min(tmn[i][j - 1], tmn[i + (1 << (j - 1))][j - 1]); tmx[i][j] = max(tmx[i][j - 1], tmx[i + (1 << (j - 1))][j - 1]); } int ls = 1; bool las = false; for(int i = 1; i <= m + 1; i++){ if(t[1] > h[i]){ nd[i] = timer; las = true; }else{ if(las){ crt(timer); ++timer; expand({timer - 1, ls, i - 1, 1}); } las = false; ls = i + 1; } } for(int i = 1; i < timer; i++) if(dad[i]) tr(i); } bool can_reach(int l, int r, int s, int d){ ++l; ++r; ++s; ++d; if (find(nd[s]) != find(nd[d])) return false; return true; return is_s(nd[s], nd[d], l, r); }