#include <bits/stdc++.h> using namespace std; const int N = 2e5 + 5; const int dN = 4e5 + 5; const int oN = 1600005; const int M = 4e5 + 5; vector<int> g[2][dN], s[oN]; int X[M], Y[M], id[M]; int p[2][dN], W[2][dN]; int up[2][dN][18], d[2][dN]; int tin[2][dN], tout[2][dN], arr[2][dN], ti[2]; int n, L1, R1, L2, R2; bool cmp0(int i, int j){ return min(X[i], Y[i]) > min(X[j], Y[j]); } bool cmp1(int i, int j){ return max(X[i], Y[i]) < max(X[j], Y[j]); } int fp(int x, int u){ return u == p[x][u] ? u : p[x][u] = fp(x, p[x][u]); } int kth(int x, int u, int k){ for(int j = 17; j >= 0; --j) if(k & (1 << j)) u = up[x][u][j]; return u; } void dfs(int x, int u, int par){ up[x][u][0] = par; tin[x][u] = ti[x]++; if(u != par) d[x][u] = d[x][par] + 1; for(int j = 1; j < 18; ++j) up[x][u][j] = up[x][ up[x][u][j-1] ][j-1]; for(int v : g[x][u]) dfs(x, v, u); tout[x][u] = ti[x] - 1; } void bld(int ind, int l, int r){ if(l == r){ if(arr[0][l] != -1) s[ind] = {arr[0][l]}; // FIX: no -1 return; } int m = (l + r) >> 1; bld(ind<<1, l, m); bld(ind<<1|1, m+1, r); merge(s[ind<<1].begin(), s[ind<<1].end(), s[ind<<1|1].begin(), s[ind<<1|1].end(), back_inserter(s[ind])); } int qry(int ind, int l, int r){ if(l > R1 || r < L1) return 0; if(L1 <= l && r <= R1){ return upper_bound(s[ind].begin(), s[ind].end(), R2) - lower_bound(s[ind].begin(), s[ind].end(), L2); } int m = (l + r) >> 1; return qry(ind<<1, l, m) + qry(ind<<1|1, m+1, r); } vector<int> check_validity( int _n, vector<int> XX, vector<int> YY, vector<int> S, vector<int> E, vector<int> L, vector<int> R ){ int m = XX.size(); n = _n; for(int i = 0; i < m; ++i){ X[i] = XX[i]; Y[i] = YY[i]; id[i] = i; } for(int x = 0; x < 2; ++x) for(int i = 0; i < 2*n; ++i) p[x][i] = i; int nn[2] = {n, n}; for(int x = 0; x < 2; ++x){ if(x == 0) sort(id, id+m, cmp0); else sort(id, id+m, cmp1); for(int i = 0; i < m; ++i){ int u = X[id[i]], v = Y[id[i]]; u = fp(x, u); v = fp(x, v); if(u != v){ g[x][nn[x]].push_back(u); g[x][nn[x]].push_back(v); p[x][u] = p[x][v] = nn[x]; W[x][nn[x]] = (x == 0 ? min(X[id[i]], Y[id[i]]) : max(X[id[i]], Y[id[i]])); nn[x]++; } } // FIX: initialize root weight W[x][nn[x]-1] = (x == 0 ? -1e9 : 1e9); ti[x] = 0; fill(arr[x], arr[x] + nn[x], -1); // FIX: handle disconnected components for(int i = 0; i < nn[x]; ++i) if(fp(x, i) == i) dfs(x, i, i); for(int i = 0; i < n; ++i) arr[x][ tin[x][i] ] = i; } // FIX: vector instead of map vector<int> mp(n, -1); for(int i = 0; i < nn[1]; ++i) if(arr[1][i] != -1) mp[arr[1][i]] = i; for(int i = 0; i < nn[0]; ++i) if(arr[0][i] != -1) arr[0][i] = mp[arr[0][i]]; bld(1, 0, nn[0]-1); int q = S.size(); vector<int> Ans(q); for(int i = 0; i < q; ++i){ int u = S[i], v = E[i]; int anc_u = -1, anc_v = -1; // FIX: correct binary search direction int lo = 0, hi = d[0][u]; while(lo <= hi){ int mid = (lo + hi) >> 1; int anc = kth(0, u, mid); if(W[0][anc] >= L[i]) anc_u = anc, hi = mid - 1; else lo = mid + 1; } lo = 0, hi = d[1][v]; while(lo <= hi){ int mid = (lo + hi) >> 1; int anc = kth(1, v, mid); if(W[1][anc] <= R[i]) anc_v = anc, hi = mid - 1; else lo = mid + 1; } if(anc_u == -1 || anc_v == -1){ Ans[i] = 0; continue; } L1 = tin[0][anc_u]; R1 = tout[0][anc_u]; L2 = tin[1][anc_v]; R2 = tout[1][anc_v]; Ans[i] = qry(1, 0, nn[0]-1) > 0; } return Ans; }