#include "obstacles.h" #include <bits/stdc++.h> using namespace std; int prnt[200005], cntv[200005]; int fixv[200005], maxtv[200005], maxtn[200005], mintv[200005], mintn[200005]; int sparseH[19][200005], sparseA[19][200005], spnomA[19][200005]; struct Gr { int A, nom; }; vector<Gr> gr; int find_set(int v){ if (prnt[v] != v) prnt[v] = find_set(prnt[v]); return prnt[v]; } void union_set(int a, int b){ a = find_set(a); b = find_set(b); if (a == b) return; if (cntv[b] > cntv[a]) swap(a,b); cntv[a] += cntv[b]; prnt[b] = a; } int getmaxH(int L, int R){ int len = R - L + 1; int k = 31 - __builtin_clz(len); return max(sparseH[k][L], sparseH[k][R+1-(1<<k)]); } int getnomA(int L, int R){ int len = R - L + 1; int k = 31 - __builtin_clz(len); int n1 = spnomA[k][R+1-(1<<k)]; int n2 = spnomA[k][L]; if (sparseA[k][L] > sparseA[k][R+1-(1<<k)]) return n2; return n1; } void initialize(vector<int> T, vector<int> H){ int N = T.size(), M = H.size(); gr.clear(); for (int i = 0; i < M; i++){ prnt[i] = i; cntv[i] = 1; fixv[i] = (H[i] < T[0]); sparseA[0][i] = -1; sparseH[0][i] = H[i]; spnomA[0][i] = i; } maxtv[0] = mintv[0] = T[0]; maxtn[0] = mintn[0] = 0; for (int i = 1; i < N; i++){ maxtv[i] = maxtv[i-1]; maxtn[i] = maxtn[i-1]; if (T[i] > maxtv[i-1]) maxtv[i] = T[i], maxtn[i] = i; mintv[i] = mintv[i-1]; mintn[i] = mintn[i-1]; if (T[i] < mintv[i-1]) mintv[i] = T[i], mintn[i] = i; } int nmin = -1, hmin = 1e9+5; if (fixv[0]) nmin = 0, hmin = H[0]; for (int i = 1; i < M; i++){ if (fixv[i]){ if (fixv[i-1]){ union_set(i, i-1); if (H[i] < hmin) hmin = H[i], nmin = i; } else { hmin = H[i]; nmin = i; } } else { if (fixv[i-1] && nmin != -1){ int A = 0, B = N - 1; while (A < B){ int C = (A + B + 1) / 2; if (mintv[C] > hmin) A = C; else B = C - 1; } if (A > 0){ gr.push_back({A, nmin}); sparseA[0][nmin] = A; } } } } int K = 31 - __builtin_clz(max(1, M)); for (int k = 1; k <= K; k++){ int half = 1 << (k - 1); for (int i = 0; i + (1<<k) <= M; i++){ sparseH[k][i] = max(sparseH[k-1][i], sparseH[k-1][i + half]); int L = spnomA[k-1][i]; int R = spnomA[k-1][i + half]; if (sparseA[k-1][L] >= sparseA[k-1][R]){ sparseA[k][i] = sparseA[k-1][L]; spnomA[k][i] = L; } else { sparseA[k][i] = sparseA[k-1][R]; spnomA[k][i] = R; } } } for (int i = 0; i < (int)gr.size(); i++){ int A = gr[i].A; int nom = gr[i].nom; int tempT = T[A]; int bestRow = maxtn[A]; if (i > 0){ int L = 0, R = nom; while (L < R){ int mid = (L+R)/2; if (getmaxH(mid, nom) >= tempT) L = mid + 1; else R = mid; } if (L < nom){ int x = getnomA(L, nom-1); if (sparseA[0][x] >= bestRow) union_set(nom, x); } } if (i + 1 < (int)gr.size()){ int L = nom, R = M - 1; while (L < R){ int mid = (L + R + 1) / 2; if (getmaxH(nom, mid) >= tempT) R = mid - 1; else L = mid; } if (L > nom){ int x = getnomA(nom+1, L); if (sparseA[0][x] >= bestRow) union_set(nom, x); } } } } bool can_reach(int L, int R, int S, int D){ return find_set(S) == find_set(D); }