#include <bits/stdc++.h>
#include "werewolf.h"
using namespace std;
#define REP(i, n) for (int i = 0; i < (n); i++)
struct Tree2D {
vector<pair<int,int>> pts;
vector<vector<int>> nodes;
int n = 0;
Tree2D(const vector<pair<int,int>>& points) {
pts = points;
sort(pts.begin(), pts.end());
n = pts.size();
nodes.resize(4*n);
build(0, 0, n-1);
}
void build(int u, int l, int r) {
if (l == r) {
nodes[u].push_back(pts[l].second);
} else {
int m = (l + r) / 2;
build(2*u+1, l, m);
build(2*u+2, m+1, r);
nodes[u].reserve(r - l + 1);
merge(nodes[2*u+1].begin(), nodes[2*u+1].end(),
nodes[2*u+2].begin(), nodes[2*u+2].end(),
back_inserter(nodes[u]));
}
}
int countNode(int u, int yl, int yr) {
// it0 --> First point at >= yl
auto it0 = lower_bound(nodes[u].begin(), nodes[u].end(), yl);
// it1 --> First element > yr
auto it1 = upper_bound(nodes[u].begin(), nodes[u].end(), yr);
return distance(it0, it1);
}
// qxl, qxr: Range of nodes in tree
int query(int u, int l, int r, int qxl, int qxr, int qyl, int qyr) {
if (r < qxl || l > qxr) {return 0;}
if (l >= qxl && r <= qxr) {
return countNode(u, qyl, qyr);
}
int m = (l + r) / 2;
return query(2 * u + 1, l, m, qxl, qxr, qyl, qyr) +
query(2 * u + 2, m + 1, r, qxl, qxr, qyl, qyr);
}
int query(int qxl, int qxr, int qyl, int qyr) {
return query(0, 0, n-1, qxl, qxr, qyl, qyr);
}
};
int fufind(vector<int>& fu, int x) {
if (fu[x] < 0) {return x;} // x is root
fu[x] = fufind(fu, fu[x]);
return fu[x];
}
// fu[u] := Parent node of u in DSU (or -1 if u is single node)
// tree[v] := left/right child nodes of v in Kruskal Reconstruction Tree
void fujoin(vector<int>& fu, vector<pair<int,int>>& tree, int x, int y) {
x = fufind(fu, x);
y = fufind(fu, y);
if (x != y) {
int p = fu.size(); // We add a new node
fu[y] = p;
fu[x] = p;
fu.push_back(-1); // Parent of p
tree.push_back(make_pair(x,y));
}
}
pair<int,int> dfs(vector<pair<int,int>>& tree, int v, int N, int& label) {
// One of original nodes
if (v < N) {
tree[v].first = tree[v].second = label;
label++;
} else {
pair<int,int> A = dfs(tree, tree[v].first, N, label);
pair<int,int> B = dfs(tree, tree[v].second, N, label);
tree[v].first = min(A.first, B.first);
tree[v].second = max(A.second, B.second);
}
return make_pair(tree[v].first, tree[v].second);
}
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 Q = S.size();
int M = X.size();
vector<int> A(Q);
vector<vector<int> > adj(N);
REP(i, M) {
adj[X[i]].push_back(Y[i]);
adj[Y[i]].push_back(X[i]);
}
vector<pair<int,int>> Lrange(Q);
vector<pair<int,int>> Rrange(Q);
vector<pair<int,int>> pts(N);
// Compute Lrange
{
vector<int> fu(N);
vector<int> idx(Q);
vector<int> repr(Q);
REP(i, N) {fu[i] = -1;}
REP(i, Q) {idx[i] = i;}
sort(idx.begin(), idx.end(), [&](int i0, int i1) {
return L[i0] > L[i1];
});
vector<pair<int,int>> tree; tree.resize(N);
int u = N-1;
REP(i, Q) {
int limit = L[idx[i]];
for (; u >= limit; --u) {
for (int v : adj[u]) {
if (v >= limit) {
fujoin(fu, tree, u, v);
}
}
}
repr[idx[i]] = fufind(fu, S[idx[i]]);
}
int label = 0;
dfs(tree, tree.size()-1, N, label);
REP(i, Q) {Lrange[idx[i]] = tree[repr[idx[i]]];}
REP(i, N) {pts[i].first = tree[i].first;}
}
{
vector<int> fu(N);
vector<int> idx(Q);
vector<int> repr(Q);
REP(i, N) {fu[i] = -1;}
REP(i, Q) {idx[i] = i;}
sort(idx.begin(), idx.end(), [&](int i0, int i1) {
return R[i0] < R[i1];
});
vector<pair<int,int>> tree; tree.resize(N);
int u = 0;
REP(i, Q) {
int limit = R[idx[i]];
for (; u <= limit; ++u) {
for (int v : adj[u]) {
if (v <= limit) {
fujoin(fu, tree, u, v);
}
}
}
repr[idx[i]] = fufind(fu, E[idx[i]]);
}
int label = 0;
dfs(tree, tree.size()-1, N, label);
REP(i, Q) {Rrange[idx[i]] = tree[repr[idx[i]]];}
REP(i, N) {pts[i].second = tree[i].second;}
}
Tree2D tree_2d(pts);
REP(i, Q) {
A[i] = tree_2d.query(Lrange[i].first, Lrange[i].second,
Rrange[i].first, Rrange[i].second) > 0;
}
return A;
}
