#pragma GCC optimize("Ofast")
#include <bits/stdc++.h>
#include "werewolf.h"
using namespace std;
using ll = long long;
using pii = pair<int, int>;
#define rep(i, k, n) for (int i = k; i < n; i++)
template<typename T>
using v = vector<T>;
const int INF = 1e9;
struct DSU {
v<int> parent;
DSU(int n) {
parent.resize(n);
rep(i, 0, n) parent[i] = i;
}
int find(int n) {
return (parent[n] == n ? n : parent[n] = find(parent[n]));
}
void join(int a, int b, v<pii>&tree) {
a = find(a);
b = find(b);
if (a != b) {
int p = parent.size();
parent[a] = parent[b] = p;
parent.push_back(p);
tree.push_back({a, b});
}
}
};
int t = 0;
pair<int, int> dfs(v<pii> &tree, int u, int N) {
if (u < N) {
tree[u] = {t, t};
t++;
}
else {
pii A = dfs(tree, tree[u].first, N);
pii B = dfs(tree,tree[u].second, N);
tree[u].first = min(A.first, B.first);
tree[u].second = max(A.second, B.second);
}
return tree[u];
}
v<pii> points;
struct SegTree {
v<v<int>> tree;
v<v<int>> pts;
SegTree(int n) {
tree.assign(4*n, {});
pts.resize(n);
rep(i, 0, n) {
pts[points[i].first].push_back(points[i].second);
}
rep(i, 0, n) {
sort(pts[i].begin(), pts[i].end());
}
build(1, 0, n-1);
}
void build(int p, int l, int r) {
if (l == r) {
tree[p] = pts[l];
}
else {
build(2*p, l, (l+r)/2);
build(2*p+1, (l+r)/2+1, r);
merge(tree[2*p].begin(), tree[2*p].end(),
tree[2*p+1].begin(), tree[2*p+1].end(),
back_inserter(tree[p]));
}
}
int query(int p, int l, int r, int xl, int xr, int yl, int yr) {
if (l > xr || r < xl) return 0;
if (xl <= l && r <= xr) {
auto it = lower_bound(tree[p].begin(), tree[p].end(), yl) - tree[p].begin();
auto it2 = upper_bound(tree[p].begin(), tree[p].end(), yr) - tree[p].begin();
return it2 - it;
}
else {
int m = (l+r)/2;
int i1 = query(2*p, l, m, xl, xr, yl, yr);
int i2 = query(2*p+1, m+1, r, xl, xr, yl, yr);
return i1 + i2;
}
}
};
v<int> check_validity(int N, v<int> X, v<int> Y, v<int> S, v<int> E, v<int> L, v<int> R) {
int M = X.size();
int Q = L.size();
L.push_back(0);
R.push_back(N-1);
S.push_back(0);
E.push_back(0);
v<pii> Lorder(Q+1);
v<pii> Rorder(Q+1);
rep(i, 0, Q+1) {
Lorder[i] = {L[i], i};
Rorder[i] = {R[i], i};
}
v<pii> vL(Q);
v<pii> vR(Q);
//vL recognition
sort(Lorder.begin(), Lorder.end(), greater<>());
DSU dsuL(N);
v<pair<int, pii>> edgesL(M);
rep(i, 0, M) {
edgesL[i] = {min(X[i], Y[i]), {X[i], Y[i]}};
}
sort(edgesL.begin(), edgesL.end(), greater<>());
int j = 0;
v<int> leadL(Q+1);
v<pii> treeL(N);
rep(i, 0, Q+1) {
while (j < M && edgesL[j].first >= Lorder[i].first) {
dsuL.join(edgesL[j].second.first, edgesL[j].second.second, treeL);
//cout << i << " " << edgesL[j].second.first << " " << edgesL[j].second.second << endl;
j++;
}
//cout << i << " " << S[Lorder[i].second] << " " << dsuL.parent[6 ] << " " << dsuL.parent.size() << endl;
leadL[Lorder[i].second] = dsuL.find(S[Lorder[i].second]);
}
t = 0;
dfs(treeL, treeL.size()-1, N);
rep(i, 0, Q) {
vL[i] = treeL[leadL[i]];
}
//vR recognition
sort(Rorder.begin(), Rorder.end());
DSU dsuR(N);
v<pair<int, pii>> edgesR(M);
rep(i, 0, M) {
edgesR[i] = {max(X[i], Y[i]), {X[i], Y[i]}};
}
sort(edgesR.begin(), edgesR.end());
j = 0;
v<int> leadR(Q+1);
v<pii> treeR(N);
rep(i, 0, Q+1) {
while (j < M && edgesR[j].first <= Rorder[i].first) {
dsuR.join(edgesR[j].second.first, edgesR[j].second.second, treeR);
j++;
}
leadR[Rorder[i].second] = dsuR.find(E[Rorder[i].second]);
}
t = 0;
dfs(treeR, treeR.size()-1, N);
rep(i, 0, Q) {
vR[i] = treeR[leadR[i]];
}
//Query preprocessing
points.resize(N);
rep(i, 0, N) {
points[i] = {treeL[i].first, treeR[i].first};
}
sort(points.begin(), points.end());
SegTree st(N);
v<int> ans(Q);
rep(i, 0, Q) {
int que = st.query(1, 0, N-1, vL[i].first, vL[i].second, vR[i].first, vR[i].second);
//cout << que << endl;
ans[i] = que > 0;
}
return ans;
}
