#include "werewolf.h"
#include <bits/stdc++.h>
using namespace std;
#pragma GCC target("popcnt")
#define ll long long
#define pll pair<ll, ll>
#define pii pair<int, int>
#define vll vector<ll>
#define vvll vector<vll>
const ll INF = 1e18;
const int MAXN = 2e5 + 5;
struct DSUTree {
vector<int> parent;
vector<pii> children;
DSUTree(int n): parent(n), children(n, {-1,-1}) {iota(parent.begin(), parent.end(), 0);}
int find(int x) {return parent[x] < 0 ? x : parent[x] = find(parent[x]);}
void unite(int x, int y) {
x = find(x);
y = find(y);
if (x == y) return;
int p = parent.size();
parent[x] = parent[y] = p;
parent.push_back(-1);
children.emplace_back(y, x);
}
};
vector<pii> rangeDFS;
int dfsTimer;
void dfsRanges(const vector<pii>& children, int v) {
if (v < rangeDFS.size()/2 + 1 && children[v].first == -1) {
rangeDFS[v] = {dfsTimer, dfsTimer};
dfsTimer++;
} else if (v >= 0) {
int l = children[v].first, r = children[v].second;
dfsRanges(children, l);
dfsRanges(children, r);
rangeDFS[v].first = min(rangeDFS[l].first, rangeDFS[r].first);
rangeDFS[v].second = max(rangeDFS[l].second, rangeDFS[r].second);
}
}
struct Tree2D {
int n, base;
vector<pii> pts;
vector<vector<int>> tree;
Tree2D(const vector<pii>& points) {
pts = points;
sort(pts.begin(), pts.end());
n = pts.size(); base = 1;
while (base < n) base <<= 1;
tree.assign(2*base, {});
for (int i = 0; i < n; i++) tree[base + i].push_back(pts[i].second);
for (int i = base - 1; i >= 1; --i) {
auto &L = tree[2*i], &R = tree[2*i+1];
tree[i].resize(L.size() + R.size());
merge(L.begin(), L.end(), R.begin(), R.end(), tree[i].begin());
}
}
int countInNode(int idx, int yL, int yR) {
auto &v = tree[idx];
int lo = lower_bound(v.begin(), v.end(), yL) - v.begin();
int hi = upper_bound(v.begin(), v.end(), yR) - v.begin();
return hi - lo;
}
int query(int xL, int xR, int yL, int yR) {
int l = lower_bound(pts.begin(), pts.end(), make_pair(xL, -1)) - pts.begin();
int r = lower_bound(pts.begin(), pts.end(), make_pair(xR+1, -1)) - pts.begin() - 1;
if (l > r) return 0;
int res = 0;
l += base; r += base;
while (l <= r) {
if (l & 1) res += countInNode(l++, yL, yR);
if (!(r & 1)) res += countInNode(r--, yL, yR);
l >>= 1; r >>= 1;
}
return res;
}
};
vector<int> check_validity(int n, vector<int> X, vector<int> Y, vector<int> S, vector<int> E, vector<int> L, vector<int> R) {
int N = n, M = X.size(), Q = S.size();
struct Edge { int u,v,w; };
vector<Edge> edgesH(M);
for (int i = 0; i < M; i++) edgesH[i] = {X[i], Y[i], min(X[i], Y[i])};
sort(edgesH.begin(), edgesH.end(), [](auto &a, auto &b){ return a.w > b.w; });
vector<int> orderL(Q);
iota(orderL.begin(), orderL.end(), 0);
sort(orderL.begin(), orderL.end(), [&](int a, int b){ return L[a] > L[b]; });
vector<int> leadH(Q);
DSUTree dsuH(N);
int ptr = 0;
for (int idx : orderL) {
while (ptr < M && edgesH[ptr].w > L[idx]) {
dsuH.unite(edgesH[ptr].u, edgesH[ptr].v);
ptr++;
}
leadH[idx] = dsuH.find(S[idx]);
}
int totalH = dsuH.parent.size();
vector<pii> childrenH = dsuH.children;
rangeDFS.assign(totalH, {-1,-1}); dfsTimer = 0;
dfsRanges(childrenH, totalH - 1);
vector<pii> rangeH(totalH);
for (int i = 0; i < totalH; i++) rangeH[i] = rangeDFS[i];
vector<pii> LR(Q);
for (int i = 0; i < Q; i++) LR[i] = rangeH[leadH[i]];
vector<Edge> edgesW(M);
for (int i = 0; i < M; i++) edgesW[i] = {X[i], Y[i], max(X[i], Y[i])};
sort(edgesW.begin(), edgesW.end(), [](auto &a, auto &b){ return a.w < b.w; });
vector<int> orderR(Q);
iota(orderR.begin(), orderR.end(), 0);
sort(orderR.begin(), orderR.end(), [&](int a, int b){ return R[a] < R[b]; });
vector<int> leadW(Q);
DSUTree dsuW(N);
ptr = 0;
for (int idx : orderR) {
while (ptr < M && edgesW[ptr].w < R[idx]) {
dsuW.unite(edgesW[ptr].u, edgesW[ptr].v);
ptr++;
}
leadW[idx] = dsuW.find(E[idx]);
}
int totalW = dsuW.parent.size();
vector<pii> childrenW = dsuW.children;
rangeDFS.assign(totalW, {-1,-1}); dfsTimer = 0;
dfsRanges(childrenW, totalW - 1);
vector<pii> rangeW(totalW);
for (int i = 0; i < totalW; i++) rangeW[i] = rangeDFS[i];
vector<pii> RR(Q);
for (int i = 0; i < Q; i++) RR[i] = rangeW[leadW[i]];
vector<pii> pts(N);
for (int i = 0; i < N; i++) pts[i] = { rangeH[i].first, rangeW[i].first };
Tree2D tree2d(pts);
vector<int> ans(Q);
for (int i = 0; i < Q; i++) {
int xl = LR[i].first, xr = RR[i].second;
int yl = RR[i].first, yr = RR[i].second;
ans[i] = (tree2d.query(xl, xr, yl, yr) > 0);
}
return ans;
}
