/*
to future me:
I have no fucking idea what the fuck is going on, I have no idea if the code should work, good luck in debugging it lmfao.
update:
there are no longer any errors, the dfs function is fucked as it goes on in an infinite loop so fix that.
*/
#include<bits/stdc++.h>
using namespace std;
const int mxN = 200000;
int seg_tree[4*mxN+1], n, color[mxN];
vector<pair<int, int>> empt[mxN];
void stree(int u, int l, int r, vector<int> &T) {
if (l >= n || r < 0 || l > r)
return;
if (l == r) {
seg_tree[u] = T[l];
return;
}
int mid = (l+r)/2;
stree(2*u, l, mid, T);
stree(2*u + 1, mid+1, r, T);
seg_tree[u] = min(seg_tree[2*u], seg_tree[2*u + 1]);
}
vector<pair<int, int>> normalized(vector<pair<int, int>> a) {
if (a.empty())
return {};
vector<pair<int, int>> ans;
ans.push_back(a[0]);
pair<int, int> p;
for (int i = 1; i < a.size(); i++)
if (ans[ans.size()-1].second == a[i].first-1) {
p.first = ans.back().first;
p.second = a[i].second;
ans.pop_back();
ans.push_back(p);
} else
ans.push_back(a[i]);
return ans;
}
vector<pair<int, int>> query(int u, int l, int r, int val) {
//cout<< '\n' << "QUERY. " << u << ' ' << l << ' ' << r << ' ' << val << ' ' << seg_tree[u] << '\n';
if (l >= n || r < 0 || l > r)
return {};
if (seg_tree[u] > val) {
//cout<< "returned\n";
return {make_pair(l, r)};
}
if (l == r)
return {};
int mid = (l+r)/2;
vector<pair<int, int>> a = query(2*u, l, mid, val);
vector<pair<int, int>> b = query(2*u + 1, mid+1, r, val);
a.insert(a.end(), b.begin(), b.end());
return a;
}
vector<pair<int, int>> transfer(vector<pair<int, int>> a, vector<pair<int, int>> b) {
vector<pair<int, int>> ans;
reverse(a.begin(), a.end());
reverse(b.begin(), b.end());
// a -> b
while (!a.empty() && !b.empty()) {
pair<int, int> A = a.back();
pair<int, int> B = b.back();
if (A.first > B.second)
b.pop_back();
else if (B.first > A.second)
a.pop_back();
else {
ans.push_back(B);
b.pop_back();
}
}
return ans;
}
void initialize(vector<int> T, vector<int> H){
n = T.size();
memset(seg_tree, INT_MAX, sizeof seg_tree);
memset(color, -1, sizeof color);
stree(1, 0, n-1, T);
for (int i = 0; i < H.size(); i++) {
//cout<< i << " :\n";
empt[i] = normalized(query(1, 0, n-1, H[i]));
//cout<< "\nempt\n";
//for (auto &[a, b] : empt[i]) {
// cout<< "\t(" << a << "; " << b << ")\n";
//}
}
vector<int> bt(H.size(), 0);
auto dfs = [&](auto &dfs, int i, int val, vector<pair<int, int>> open) -> void {
//cout<< "DFS. " << i << " -> " << val << '\n';
//for (auto &[a, b] : open)
// cout<< "\t(" << a << "; " << b << ")\n";
if (!open.empty() && open[0].first == 0) {
// cout<< "MARKED " << i << '\n';
color[i] = val;
}
if (bt[i] > empt[i].size() || open.empty() || i < 0 || i >= H.size())
return;
bt[i]++;
vector<pair<int, int>> l, r;
if (i > 0)
l = transfer(open, empt[i-1]);
if (i < H.size()-1)
r = transfer(open, empt[i+1]);
dfs(dfs, i-1, val, l);
dfs(dfs, i+1, val, r);
};
for (int i = 0; i < H.size(); i++) {
if (T[0] > H[i] && color[i] == -1) {
vector<pair<int, int>> opn = empt[i];
while (opn.size() > 1)
opn.pop_back();
bt.resize(H.size(), 0);
//cout<< "DFS FROM : " << i << '\n';
dfs(dfs, i, i, opn);
//cout<< '\n';
}
}
//cout<< "COLOR :\n";
//for (int i = 0; i < H.size(); i++)
// cout<< color[i] << ' ';
//cout<< '\n';
}
bool can_reach(int L, int R, int S, int D){
return (color[S] == color[D]);
}
