#include "werewolf.h"
#include <bits/stdc++.h>
using namespace std;
struct disj {
vector<int> p;
disj(int n) {
p.resize(n);
iota(p.begin(), p.end(), 0);
}
int par(int n) {
return (p[n] == n)? n : p[n] = par(p[n]);
}
};
struct graph {
vector<vector<int>> G;
graph(int n) {
G.resize(n);
}
inline void add_edge(int a, int b) {
G[a].emplace_back(b);
}
void dfs(int n, vector<pair<int, int>> &euler_tour, vector<int> &euler) {
euler_tour[n].first = euler.size();
euler.emplace_back(n);
for (auto &i : G[n]) {
dfs(i, euler_tour, euler);
}
euler_tour[n].second = euler.size() - 1;
}
};
struct solver {
struct event {
int x, y1, y2, type, idx;
bool operator < (const event &b) const {
return x < b.x || (x == b.x && type < b.type);
}
};
struct bit {
vector<int> tree;
bit() {}
void init(int n) {
tree.assign(n + 1, 0);
}
void upd(int n, int x) {
for (int i = n + 1; i < tree.size(); i += i&-i) {
tree[i] += x;
}
}
int ask(int n) {
int res = 0;
for (int i = n + 1; i > 0; i -= i&-i) {
res += tree[i];
}
return res;
}
} bit;
vector<event> e;;
solver(int n) {
bit.init(n);
}
inline void add_point(int x, int y) {
e.push_back({x, y, -1, 0, -1}); //add point
}
inline void add_query(int x1, int x2, int y1, int y2, int id) {
e.push_back({x1, y1, y2, -1, id}); //from
e.push_back({x2, y1, y2, +1, id}); //to
}
void line_sweep(vector<int> &res) {
sort(e.begin(), e.end());
for (auto &k : e) {
if (k.type == -1) {
res[k.idx] -= bit.ask(k.y2) - bit.ask(k.y1 - 1);
} else if (k.type == 0) {
bit.upd(k.y1, +1);
} else if (k.type == +1) {
res[k.idx] += bit.ask(k.y2) - bit.ask(k.y1 - 1);
}
}
}
};
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 M = X.size(), Q = S.size();
/* create a rooted tree, such that any node u can reach its subtrees for L and R */
disj dsL(N), dsR(N);
graph lowerL(N), upperR(N);
vector<vector<int>> pending_edgeL(N), pending_edgeR(N);
vector<vector<int>> binary_liftL(N, vector<int>(20, -1)), binary_liftR(N, vector<int>(20, -1));
for (int i = 0; i < M; i++) {
if (X[i] > Y[i]) swap(X[i], Y[i]);
pending_edgeL[X[i]].emplace_back(Y[i]);
pending_edgeR[Y[i]].emplace_back(X[i]);
}
/* build tree for L, iterating high vertices first (most limited if L is high) */
for (int i = N - 1; i >= 0; i--) {
for (auto &j : pending_edgeL[i]) {
int p = dsL.par(j);
if (i == p) continue;
dsL.p[p] = i;
binary_liftL[p][0] = i;
lowerL.add_edge(i, p);
}
}
/* do the same for tree R */
for (int i = 0; i < N; i++) {
for (auto &j : pending_edgeR[i]) {
int p = dsR.par(j);
if (i == p) continue;
dsR.p[p] = i;
binary_liftR[p][0] = i;
upperR.add_edge(i, p);
}
}
/* create euler tour -> represent the graph with intervals */
vector<pair<int, int>> intervalL(N), intervalR(N);
vector<int> eulerL, eulerR;
lowerL.dfs(0, intervalL, eulerL);
upperR.dfs(N - 1, intervalR, eulerR);
vector<int> other_name(N);
for (int i = 0; i < N; i++) {
other_name[eulerR[i]] = i;
}
/* fenwick tree + line sweep technique to solve, decompose if (intervalL[i] == intervalR[j]) add point (i, j), then check for rectangle for each query */
solver Solver(N);
for (int i = 0; i < N; i++) {
Solver.add_point(i, other_name[eulerL[i]]); //get indexes intervalL in intervalR
}
/* create binary lifting for each query S and E, find minimum from S and maximum from E (vertex number) */
for (int j = 1; j < 20; j++) {
for (int i = 0; i < N; i++) {
if (binary_liftL[i][j - 1] != -1) binary_liftL[i][j] = binary_liftL[binary_liftL[i][j - 1]][j - 1];
if (binary_liftR[i][j - 1] != -1) binary_liftR[i][j] = binary_liftR[binary_liftR[i][j - 1]][j - 1];
}
}
for (int i = 0; i < Q; i++) { //get updates, lift S and E with binary lifting
int s = S[i], e = E[i];
for (int j = 19; j >= 0; j--) { //binary lifting
if (binary_liftL[s][j] != -1 && L[i] <= binary_liftL[s][j]) s = binary_liftL[s][j];
if (binary_liftR[e][j] != -1 && binary_liftR[e][j] <= R[i]) e = binary_liftR[e][j];
}
Solver.add_query(intervalL[s].first, intervalL[s].second, intervalR[e].first, intervalR[e].second, i);
}
vector<int> res(Q, 0); Solver.line_sweep(res);
for (int i = 0; i < Q; i++) res[i] = (res[i] > 0);
return res;
}
