#include "obstacles.h"
#include <bits/stdc++.h>
using namespace std;
#define m_p make_pair
#define all(x) (x).begin(),(x).end()
#define sz(x) ((int)(x).size())
#define fi first
#define se second
typedef long long ll;
mt19937 rnd(chrono::steady_clock::now().time_since_epoch().count());
mt19937 rnf(2106);
const int N = 200005, INF = 1000000009, k = 18;
int n, m;
int p[N], pl[N], pr[N];
int maxh[N * 4];
pair<int, int> minh[N * 4];
void bil(const vector<int>& H, int tl, int tr, int pos)
{
if (tl == tr)
{
maxh[pos] = H[tl];
minh[pos] = m_p(H[tl], tl);
return;
}
int m = (tl + tr) / 2;
bil(H, tl, m, pos * 2);
bil(H, m + 1, tr, pos * 2 + 1);
maxh[pos] = max(maxh[pos * 2], maxh[pos * 2 + 1]);
minh[pos] = min(minh[pos * 2], minh[pos * 2 + 1]);
}
int qrymax(int tl, int tr, int l, int r, int pos)
{
if (l > r)
return -1;
if (tl == l && tr == r)
return maxh[pos];
int m = (tl + tr) / 2;
return max(qrymax(tl, m, l, min(m, r), pos * 2),
qrymax(m + 1, tr, max(m + 1, l), r, pos * 2 + 1));
}
pair<int, int> qrymin(int tl, int tr, int l, int r, int pos)
{
if (l > r)
return m_p(INF, INF);
if (tl == l && tr == r)
return minh[pos];
int m = (tl + tr) / 2;
return min(qrymin(tl, m, l, min(m, r), pos * 2),
qrymin(m + 1, tr, max(m + 1, l), r, pos * 2 + 1));
}
vector<int> gg[N];
int pp[N][k];
void dfs(int x, int p)
{
pp[x][0] = p;
for (int i = 1; i < k; ++i)
pp[x][i] = pp[pp[x][i - 1]][i - 1];
for (int i = 0; i < gg[x].size(); ++i)
{
int h = gg[x][i];
if (h == p)
continue;
dfs(h, x);
}
}
int ppl[N][k], ppr[N][k];
void initialize(std::vector<int> T, std::vector<int> H)
{
n = sz(T);
m = sz(H);
vector<int> mint(sz(T)), maxt(sz(T));
mint[0] = T[0];
for (int i = 1; i < sz(T); ++i)
mint[i] = min(mint[i - 1], T[i]);
maxt[0] = T[0];
for (int i = 1; i < sz(T); ++i)
maxt[i] = max(maxt[i - 1], T[i]);
bil(H, 0, m - 1, 1);
for (int j = 0; j < m; ++j)
{
if (H[j] >= T[0])
{
p[j] = pl[j] = pr[j] = j;
continue;
}
int l = 1, r = n - 1;
int t = T[0];
while (l <= r)
{
int mid = (l + r) / 2;
if (mint[mid] > H[j])
{
t = maxt[mid];
l = mid + 1;
}
else
r = mid - 1;
}
l = j;
r = m - 1;
int ur = -1;
while (l <= r)
{
int mid = (l + r) / 2;
if (qrymax(0, m - 1, j, mid, 1) < t)
{
ur = mid;
l = mid + 1;
}
else
r = mid - 1;
}
assert(ur != -1);
l = 0;
r = j;
int ul = -1;
while (l <= r)
{
int mid = (l + r) / 2;
if (qrymax(0, m - 1, mid, j, 1) < t)
{
ul = mid;
r = mid - 1;
}
else
l = mid + 1;
}
assert(ul != -1);
pair<int, int> pl = qrymin(0, m - 1, ul, j, 1);
pair<int, int> pr = qrymin(0, m - 1, j, ur, 1);
::pl[j] = pl.se;
::pr[j] = pr.se;
p[j] = min(pl, pr).se;
}
for (int j = 0; j < m; ++j)
{
if (j != pl[j])
gg[pl[j]].push_back(j);
}
for (int j = 0; j < m; ++j)
{
if (j == pl[j])
dfs(j, j);
}
memcpy(ppl, pp, sizeof pp);
for (int j = 0; j < m; ++j)
gg[j].clear();
for (int j = 0; j < m; ++j)
{
if (j != pr[j])
gg[pr[j]].push_back(j);
}
for (int j = 0; j < m; ++j)
{
if (j == pr[j])
dfs(j, j);
}
memcpy(ppr, pp, sizeof pp);
for (int j = 0; j < m; ++j)
gg[j].clear();
for (int j = 0; j < m; ++j)
{
if (j != p[j])
gg[p[j]].push_back(j);
}
for (int j = 0; j < m; ++j)
{
if (j == p[j])
dfs(j, j);
}
}
int go(int x, int l, int r)
{
return pp[x][k - 1];
}
bool can_reach(int L, int R, int S, int D)
{
return go(S, L, R) == go(D, L, R);
}
/*
3 4
2 1 3
0 1 2 0
1
0 3 1 3
*/
