#include "werewolf.h"
#include <bits/stdc++.h>
using namespace std;
// Disjoint Set
vector<int> disj;
int Find(int x) {
return disj[x] == x ? x : disj[x] = Find(disj[x]);
}
class BIT {
private:
int sz;
vector<int> tree;
void Update_(int p, int x) {
for (int i = p + 1; i <= sz; i += (i & -i)) {
tree[i - 1] += x;
}
}
int Query_(int p) {
int res = 0;
for (int i = p + 1; i > 0; i -= (i & -i)) {
res += tree[i - 1];
}
return res;
}
public:
BIT() {}
BIT(int n) : sz(n) { tree.assign(sz, 0); }
void Update(int p, int x) {
return Update_(p, x);
}
int Query(int L, int R) {
return Query_(R) - Query_(L - 1);
}
};
// Line Sweep
struct Event {
int type; // 0 (point), 1 (query end), -1 (query start)
int lo, hi;
int id;
Event() {}
Event(int t, int l, int h, int i) : type(t), lo(l), hi(h), id(i) {}
bool operator < (const Event &o) const { return type < o.type; }
};
vector<vector<Event>> events;
void AddPoint(int x, int y) {
events[x].emplace_back(0, y, y, -1);
}
void AddQuery(int x_1, int x_2, int y_1, int y_2) {
static int id_ = 0;
events[x_1].emplace_back(-1, y_1, y_2, id_);
events[x_2].emplace_back(+1, y_1, y_2, id_);
id_++;
}
void LineSweep(int n, vector<int> &InsideRectangle) {
BIT tree(n);
for (int x = 0; x < n; x++) {
sort(begin(events[x]), end(events[x]));
for (auto e : events[x]) {
if (e.type == 0) { // Add Point
tree.Update(e.lo, +1);
} else { // Process Query
InsideRectangle[e.id] += e.type * tree.Query(e.lo, e.hi);
}
}
}
}
vector<int> check_validity(int N, vector<int> X, vector<int> Y, vector<int> S,
vector<int> E, vector<int> L, vector<int> R) {
disj.resize(N), events.resize(2 * N);
vector<vector<int>> adj(N);
for (int i = 0; i < (int) X.size(); i++) {
adj[X[i]].emplace_back(Y[i]);
adj[Y[i]].emplace_back(X[i]);
}
vector<int> LineL, LineR;
vector<vector<int>> AncL(N, vector<int>(20, -1)), AncR(N, vector<int>(20, -1));
function<void(int, vector<vector<int>>&, vector<vector<int>>&, vector<int>&)> dfs = [&](
int n, vector<vector<int>> &adjList, vector<vector<int>> &anc, vector<int> &v) {
v.emplace_back(n);
for (int j = 1; j < 20; j++) {
if (anc[n][j - 1] != -1) {
anc[n][j] = anc[anc[n][j - 1]][j - 1];
}
}
for (auto i : adjList[n]) {
anc[i][0] = n;
dfs(i, adjList, anc, v);
}
v.emplace_back(n);
};
{ // Created rooted tree for L (low-population restricted)
iota(begin(disj), end(disj), 0);
vector<vector<int>> tree(N);
for (int u = N - 1; u >= 0; u--) {
for (auto v : adj[u]) {
if (v < u) continue;
if (u == Find(v)) continue;
tree[u].emplace_back(Find(v));
disj[Find(v)] = u;
}
}
AncL[0][0] = -1;
dfs(0, tree, AncL, LineL);
}
{ // Created rooted tree for R (high-population restricted)
iota(begin(disj), end(disj), 0);
vector<vector<int>> tree(N);
for (int u = 0; u < N; u++) {
for (auto v : adj[u]) {
if (v > u) continue;
if (u == Find(v)) continue;
tree[u].emplace_back(Find(v));
disj[Find(v)] = u;
}
}
AncR[N - 1][0] = -1;
dfs(N - 1, tree, AncR, LineR);
}
vector<pair<int, int>> posL(N, {-1, -1}), posR(N, {-1, -1});
for (int i = 0; i < 2 * N; i++) {
if (posL[LineL[i]].first == -1) {
posL[LineL[i]].first = i;
} else {
posL[LineL[i]].second = i;
}
if (posR[LineR[i]].first == -1) {
posR[LineR[i]].first = i;
} else {
posR[LineR[i]].second = i;
}
}
for (int i = 0; i < N; i++) {
AddPoint(posL[i].first, posR[i].first);
}
int Q = L.size();
for (int i = 0; i < Q; i++) {
int s = S[i];
int e = E[i];
for (int j = 19; j >= 0; j--) {
if (AncL[s][j] != -1 && AncL[s][j] >= L[i]) s = AncL[s][j];
if (AncR[e][j] != -1 && AncR[e][j] <= R[i]) e = AncR[e][j];
}
AddQuery(posL[s].first, posL[s].second, posR[e].first, posR[e].second);
}
vector<int> res(Q, 0);
LineSweep(2 * N, res);
for (int i = 0; i < Q; i++) res[i] = res[i] > 0;
return res;
}
