#include <iostream> #include <vector> #include <cmath> #include <set> #include <map> #include <algorithm> using namespace std; #define all(x) x.begin(), x.end() #define rall(x) x.rbegin(), x.rend() #define uniq(x) x.resize(unique(all(x)) - x.begin()) #define sort_uniq(x) sort(all(x)), uniq(x) #define no_el(x, y) x.find(y) == x.end() #define ll long long #define pii pair<int, int> #define pll pair<ll, ll> #define V vector #define pb push_back #define eb emplace_back #define FASTIO ios_base::sync_with_stdio(false); cin.tie(nullptr); cout.tie(nullptr); #define INF INT32_MAX #define blt __builtin_popcount #define sz(x) int(x.size()) #define rep(a, b, c, d) for (int a = b; a <= c; a += d) #define repl(a, b, c, d) for (int a = b; a >= c; a -= d) #define ld long double struct node{ int ind, l, r, t; }; const int N = 2e5 + 5; const int LG = 19; int n, m; V<int> t, h; int stmn[N][LG], stmx[N][LG], tmn[N][LG], tmx[N][LG], lg2[N], nd[N]; V<node> v; int p[N]; int sz[N]; bool vis[N * LG]; int timer = 1; map<tuple<int, int, int>, int> mp; void crt(int x) { p[x] = x; sz[x] = 1; } int find(int x) { if (x == p[x]) return x; return p[x] = x; } void merge(int a, int b) { a = find(a), b = find(b); if (a == b) { return; } if (sz[a] < sz[b]) swap(a, b); sz[a] += sz[b]; p[b] = a; } int min_rng(int l, int r) { int j = lg2[r - l + 1]; return min(stmn[l][j], stmn[r - (1 << j) + 1][j]); } int max_rng(int l, int r) { int j = lg2[r - l + 1]; return max(stmx[l][j], stmx[r - (1 << j) + 1][j]); } int mnt_rng(int l, int r) { int j = lg2[r - l + 1]; return min(tmn[l][j], tmn[r - (1 << j) + 1][j]); } int mxt_rng(int l, int r) { int j = lg2[r - l + 1]; return max(tmx[l][j], tmx[r - (1 << j) + 1][j]); } void up(node x) { vis[x.ind] = true; if (x.l == 1 && x.r == m) return; if (x.t == n) return; int vl = min(h[x.l - 1], h[x.r - 1]); if (mxt_rng(x.t + 1, n) <= vl) return; int l = x.t + 1, r = n - 1, ans = n; while (l <= r) { int md = l + r >> 1; if (mxt_rng(x.t + 1, md) <= vl) { l = md + 1; } else { r = md - 1; ans = md; } } if (mnt_rng(x.t + 1, ans) <= min_rng(x.l, x.r)) return; int nwt = ans; l = 1, r = x.l - 1, ans = x.l; while (l <= r) { int md = l + r >> 1; if (max_rng(md, x.l) < t[nwt]) { r = md - 1; ans = md; } else { l = md + 1; } } int nwl = ans; l = x.r + 1, r = m, ans = x.r; while (l <= r) { int md = l + r >> 1; if (max_rng(x.r, md) < t[nwt]) { l = md + 1; ans = md; } else { r = md - 1; } } int nwr = ans; if (mp.find({nwt, nwl, nwr}) != mp.end()) { merge(x.ind, mp[{nwt, nwl, nwr}]); } else { mp[{nwt, nwl, nwr}] = timer; crt(timer); ++timer; merge(x.ind, mp[{nwt, nwl, nwr}]); up({timer - 1, nwl, nwr, nwt}); } } void initialize(std::vector<int> T, std::vector<int> H) { n = sz(T), m = sz(H); t.resize(n + 1), h.resize(m + 1); rep(i, 1, n, 1) t[i] = T[i - 1]; rep(i, 1, m, 1) h[i] = H[i - 1]; rep(i, 1, m, 1) { stmn[i][0] = h[i]; stmx[i][0] = h[i]; } rep(j, 1, LG - 1, 1) { rep(i, 1, m, 1) { int nx = i + (1 << (j - 1)); if (nx <= m) { stmn[i][j] = min(stmn[i][j - 1], stmn[nx][j - 1]); stmx[i][j] = max(stmx[i][j - 1], stmx[nx][j - 1]); } else { stmn[i][j] = stmn[i][j - 1]; stmx[i][j] = stmx[i][j - 1]; } } } rep(i, 1, m, 1) { tmn[i][0] = t[i]; tmn[i][0] = t[i]; } rep(j, 1, LG - 1, 1) { rep(i, 1, m, 1) { int nx = i + (1 << (j - 1)); if (nx <= m) { tmn[i][j] = min(tmn[i][j - 1], tmn[nx][j - 1]); tmn[i][j] = max(tmn[i][j - 1], tmn[nx][j - 1]); } else { tmn[i][j] = tmn[i][j - 1]; tmn[i][j] = tmn[i][j - 1]; } } } lg2[1] = 0; rep(i, 2, N - 1, 1) { lg2[i] = lg2[i >> 1] + 1; } int ls = 1; bool las = false; rep(i, 1, m, 1) { if (t[1] > h[i]) { nd[i] = timer; las = true; } else { if (las) { v.pb({timer, ls, i - 1, 1}); ++timer; } ls = i + 1; } } for (node x : v) { crt(x.ind); up(x); } } bool can_reach(int l, int r, int s, int d) { if (find(nd[s]) == find(nd[d])) return true; else return false; }