#include "obstacles.h"
#include <bits/stdc++.h>
using namespace std;
struct segment {
vector<pair<int,int>> tr_max;
vector<int> tr_min;
int sz = 1;
int n;
int MIN = -1e9 - 1;
void build(int v, int l, int r, vector<int> &vec) {
if(r-l == 1) {
tr_max[v] = {vec[l], l};
tr_min[v] = vec[l];
return;
}
int m = (l+r)/2;
build(2*v, l, m, vec);
build(2*v+1, m, r, vec);
tr_max[v] = max(tr_max[2*v], tr_max[2*v+1]);
tr_min[v] = min(tr_min[2*v], tr_min[2*v+1]);
}
segment(vector<int> &v) {
n = v.size();
while(sz < n) sz *= 2;
tr_max.assign(2*sz, {MIN, -1});
tr_min.assign(2*sz, -MIN);
build(1, 0, n, v);
}
pair<int,int> mx(int v, int l, int r, int ql, int qr) {
if(l >= qr or r <= ql) return {MIN, -1};
if(l >= ql and r <= qr) return tr_max[v];
int m = (l+r)/2;
return max(mx(2*v, l, m, ql, qr), mx(2*v+1, m, r, ql, qr));
}
pair<int,int> mx(int l, int r) {
return mx(1, 0, n, l, r);
}
int nse(int v, int l, int r, int ql, int qr, int val) {
if(l >= qr or r <= ql or tr_min[v] > val) return -1;
if(r - l == 1) return l;
int m = (l+r)/2;
int x = nse(2*v, l, m, ql, qr, val);
if(x != -1) return x;
return nse(2*v+1, m, r, ql, qr, val);
}
int nse(int l, int r, int val) {
return nse(1, 0, n, l, r, val);
}
int pse(int v, int l, int r, int ql, int qr, int val) {
if(l >= qr or r <= ql or tr_min[v] > val) return -1;
if(r - l == 1) return l;
int m = (l+r)/2;
int x = pse(2*v+1, m, r, ql, qr, val);
if(x != -1) return x;
return pse(2*v, l, m, ql, qr, val);
}
int pse(int l, int r, int val) {
return pse(1, 0, n, l, r, val);
}
};
vector<int> cc;
void initialize(std::vector<int> T, std::vector<int> H) {
int N = T.size(), M = H.size();
segment vert(T);
vector<int> max_T(M);
for(int i=0; i<M; i++) {
int r = vert.nse(0, N, H[i]);
if(r == -1) r = N;
max_T[i] = vert.mx(0, r).first;
}
// for(int x: vert.tr_min) cout << x << endl;
auto neg_H = H;
for(int i=0; i<M; i++) neg_H[i] = -H[i];
segment hor(neg_H);
vector<vector<int>> ad(M);
for(int i=0; i<M; i++) {
int l = hor.pse(0, i+1, -max_T[i]);
if(l == -1) l = -1;
int r = hor.nse(i, N, -max_T[i]);
if(r == -1) r = M;
int j = hor.mx(l+1, r).second;
// cerr << "range: " << l << " " << r << endl;
// cerr << i << " " << j << endl;
if(j == -1) continue;
if(H[j] > H[i]) continue;
ad[i].push_back(j);
ad[j].push_back(i);
}
vector<int> vis(M);
auto dfs = [&](auto &&self, int v, int c) -> void {
vis[v] = 1;
cc[v] = c;
for(int u: ad[v]) {
if(vis[u]) continue;
self(self, u, c);
}
};
int ct = 0;
cc.resize(M);
for(int i=0; i<M; i++) {
if(vis[i]) continue;
dfs(dfs, i, ct++);
}
}
bool can_reach(int L, int R, int S, int D) {
return cc[S] == cc[D];
}
