#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; //cout<< "\tLEFTMOST : " << mid << " -> " << sl << " : " << mxquery(mid, sl+1) << '\n'; //cout<< "\t\t" << l << ' ' << r << '\n'; if (mxquery(mid, sl+1) >= val) l = mid+1; else { r = mid; } } ans.first = l; //cout<< "\tLEFTMOSTEND : " << l << ' ' << mid << ' ' << r << '\n'; l = sr; r = n-1; //cout<< '\n'; while (l < r) { mid = (l+r)/2; //cout<< "\tRIGHTMOST : " << sr << " -> " << mid << " : " << mxquery(sr, mid+1) << '\n'; //cout<< "\t\t" << l << ' ' << r << '\n'; if (mxquery(sr, mid+1) >= val) r = mid; else { l = mid+1; } } ans.second = l; if (h[ans.second] >= val) ans.second--; //cout<< "\tRIGHTMOSTEND : " << l << ' ' << mid << ' ' << r << '\n'; 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(); 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])); } /* cout<< "INC :\n\t"; for (int e : inc) cout<< e << ' '; cout<< '\n'; */ 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 = tree.query(seg_l, seg_r); int lv; while (l < r) { mid = (l+r)/2; if (mx[inc[mid]] <= mn) r = mid; else { lv = mid; l = mid+1; } } //cout<< seg_l << " -> " << seg_r << "; " << T[inc[lv]] << " :\n"; 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; } /* cout<< "REACH :\n"; for (int i = 0; i < H.size(); i++) cout<< i << " -> (" << reach[i].first << "; " << reach[i].second << ")\n"; */ } bool can_reach(int L, int R, int S, int D) { if (S == D || reach[S].first == reach[D].first && reach[S].second == reach[D].second) return true; int lv = max(lvl[S], lvl[D]); int l = max(reach[S].first, reach[D].first); int r = min(reach[S].second, reach[D].second); if (l > r) return false; int mn = tree.query(l, r); return (mn < mx[max(0, lv-1)]); }