#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);
}
