#include<bits/stdc++.h> using namespace std; #define pb push_back class seg_tree { private: int n; int tree[800000], mxtree[800000]; vector<int> h; void build(int u, int l, int r, vector<int> &v) { if (l > r || r < 0 || l >= n) return; if (l == r) { tree[u] = v[l]; return; } int mid = (l+r)/2; build(2*u, l, mid, v); build(2*u + 1, mid+1, r, v); tree[u] = min(tree[2*u], tree[2*u + 1]); } void mxbuild(int u, int l, int r, vector<int> &v) { if (l > r || r < 0 || l >= n) return; if (l == r) { mxtree[u] = v[l]; return; } int mid = (l+r)/2; mxbuild(2*u, l, mid, v); mxbuild(2*u + 1, mid+1, r, v); mxtree[u] = max(mxtree[2*u], mxtree[2*u + 1]); } int query(int u, int l, int r, int ql, int qr) { if (r < ql || l > qr) return (int)(1e9); if (ql <= l && qr >= r) return tree[u]; if (l == r) return (int)(1e9); int mid = (l+r)/2; return min(query(2*u, l, mid, ql, qr), query(2*u + 1, mid+1, r, ql, qr)); } int mxquery(int u, int l, int r, int ql, int qr) { if (r < ql || l > qr) return (int)(-1e9); if (ql <= l && qr >= r) return mxtree[u]; if (l == r) return (int)(-1e9); int mid = (l+r)/2; return max(mxquery(2*u, l, mid, ql, qr), mxquery(2*u + 1, mid+1, r, ql, qr)); } public: void build(vector<int> v) { n = v.size(); build(1, 0, n-1, v); mxbuild(1, 0, n-1, v); h = v; } int query(int l, int r) { return query(1, 0, n-1, l, r); } int mxquery(int l, int r) { return mxquery(1, 0, n-1, l, r); } pair<int, int> open(int sl, int sr, int val) { int l = 0, r = sl, mid; pair<int, int> ans; while (l < r) { mid = (l+r)/2; if (mxquery(mid, sl) >= val) l = mid+1; else r = mid; } ans.first = l; l = sr; r = n-1; while (l < r) { mid = (l+r)/2; if (mxquery(sr, mid) >= val) r = mid; else { l = mid+1; } } ans.second = l; if (h[ans.second] >= val) ans.second--; return ans; } }; pair<int, int> reach[200000]; int lvl[200000]; vector<int> inc = {0}, mx, t; seg_tree tree; void initialize(vector<int> T, vector<int> H) { int hmx = H[0]; for (int e : H) hmx = max(hmx, e); for (int i = 0; i < T.size(); i++) if (T[i] > hmx) while (T.size() > i+1) T.pop_back(); int mnn = H[0]; for (int e : H) mnn = min(mnn, e); t = T; tree.build(H); mx.pb(T[0]); for (int i = 1; i < T.size(); i++) { if (T[inc.back()] < T[i]) { if (!inc.empty() && inc.back()+1 == i) inc[inc.size()-1] = i; else inc.pb(i); } mx.pb(min(mx.back(), T[i])); } for (int i = 0; i < H.size(); i++) { if (H[i] >= T[0]) { reach[i].first = -1; reach[i].second = -1; continue; } int j = i; while (j+1 < H.size() && H[j+1] < T[0]) j++; int seg_l = i, seg_r = j; int l = 0, r = inc.size(), mid, mn = mnn; int lv = 0; bool fl = true; while (l < r) { mid = (l+r)/2; if (mx[inc[mid]] <= mn) r = mid; else { lv = mid; l = mid+1; } } pair<int, int> rch = tree.open(seg_l, seg_r, T[inc[lv]]); seg_l = rch.first; seg_r = rch.second; for (int ind = i; ind <= j; ind++) { lvl[ind] = inc[lv]; reach[ind].first = seg_l; reach[ind].second = seg_r; } i = j; } } bool can_reach(int L, int R, int S, int D) { if (reach[S].first == reach[D].first && reach[S].second == reach[D].second) return true; return false; }