#include "obstacles.h"
#include <bits/stdc++.h>
using namespace std;
#define ll long long
int MAXM = 2e5+5;
struct UF {
vector<int> key, sz;
UF(int n) {
for (int i = 0; i <= n; i++) {
key.push_back(i);
sz.push_back(1);
}
}
int find(int x) {return key[x] == x ? x : key[x] = find(key[x]);}
void unite(int a, int b) {
a = find(a), b = find(b);
if (a==b) return;
if (sz[a] < sz[b]) swap(a, b);
sz[a] += sz[b];
key[b] = a;
}
};
UF comps(MAXM);
void initialize(vector<int> T, vector<int> H) {
int n = T.size(), m = H.size();
//row with highest temp of the top i
vector<int> premn(n, 0), premx(n, 0);
premn[0] = T[0];
for (int i = 1; i < n; i++) premn[i] = min(T[i], premn[i-1]);
premx[0] = 0;
for (int i = 1; i < n; i++) premx[i] = (T[i] > T[premx[i-1]] ? i : premx[i-1]);
//highest temp row we can reach from col i by going straight down
vector<int> optrow(m);
for (int i = 0; i < m; i++) {
if (T[0] <= H[i]) optrow[i] = -1;
else {
int l = 0, r = n-1;
while (l < r) {
int md = (l + r + 1) / 2;
if (premn[md] <= H[i]) r = md-1;
else l = md;
}
optrow[i] = premx[l];
}
}
//sparse table for rmq of H[i]
vector<vector<int>> mnst(20, vector<int>(m)), mxst(20, vector<int>(m));
for (int i = 0; i < m; i++) mnst[0][i] = mxst[0][i] = i;
for (int b = 1; b < 20; b++) for (int i = 0; i < m; i++) {
int j = i + (1<<(b-1));
if (j >= m) {
mnst[b][i] = mnst[b-1][i];
mxst[b][i] = mxst[b-1][i];
}
else {
mnst[b][i] = (H[mnst[b-1][i]] < H[mnst[b-1][j]] ? mnst[b-1][i] : mnst[b-1][j]);
mxst[b][i] = (H[mxst[b-1][i]] > H[mxst[b-1][j]] ? mxst[b-1][i] : mxst[b-1][j]);
}
}
auto qry = [&](int l, int r, bool mn) -> int {
int b = 20;
while ((1<<b) > r - l + 1) b--;
if (mn) return (H[mnst[b][l]] < H[mnst[b][r - (1<<b) + 1]] ? mnst[b][l] : mnst[b][r - (1<<b) + 1]);
else return (H[mxst[b][l]] > H[mxst[b][r - (1<<b) + 1]] ? mxst[b][l] : mxst[b][r - (1<<b) + 1]);
};
//now we need to somehow unite everything in our dsu
//we maintain for each col, what the furthest left and right we can go in that interval is
vector<int> mostleft(m, -1), mostright(m, -1);
for (int i = 0; i < m; i++) {
if (optrow[i] == -1) continue;
int t = T[optrow[i]];
int l = 0, r = i;
while (l < r) {
int md = (l + r) / 2;
if (H[qry(md, i, 0)] >= t) l = md+1;
else r = md;
}
mostleft[i] = l;
l = i, r = m-1;
while (l < r) {
int md = (l + r + 1) / 2;
if (H[qry(i, md, 0)] >= t) r = md-1;
else l = md;
}
mostright[i] = l;
}
//now imagine the process as jumping up segemnts, each being associated with its deepest col, so we have a tree on cols
//the parent of a col is the best col within its segment, then we simply do UF
for (int i = 0; i < m; i++) {
if (optrow[i] == -1) {
comps.unite(i, 2e5+3);
continue;
}
int p = qry(mostleft[i], mostright[i], 1);
comps.unite(i, p);
}
}
bool can_reach(int L, int R, int S, int D) {
if (comps.find(S) == comps.find(2e5+3)) return false;
return comps.find(S) == comps.find(D);
}
