#include <bits/stdc++.h>
#include "werewolf.h"
using namespace std;
#define FOR(i, a, b) for (int i = (a), _b = (b), dir = ((a) <= (b)); dir ? i <= _b : i >= _b; dir ? ++i : --i)
#define sz(v) (int) (v).size()
#define pb(v) push_back(v)
struct KRT
{
int N, LG;
vector<vector<int>> child;
vector<int> parent;
vector<int> tin, tout;
vector<int> euler;
vector<vector<int>> up;
KRT(int n = 0)
{
init(n);
}
void init(int n)
{
N = n;
child.assign(N + 1, {});
parent.assign(N + 1, 0);
tin.assign(N + 1, 0);
tout.assign(N + 1, 0);
euler.assign(N + 1, 0);
LG = 0; while ((1 << LG) <= N) ++LG;
up.assign(LG, vector<int>(N + 1, 0));
}
void buildLift()
{
FOR(u, 1, N) up[0][u] = parent[u];
FOR(i, 1, LG - 1) FOR(u, 1, N) up[i][u] = up[i - 1][up[i - 1][u]];
}
void buildEuler()
{
int dfsTimer = 0;
vector<int> it(N + 1, 0);
vector<int> st;
st.pb(0);
while (!st.empty())
{
int u = st.back();
if (u && !it[u])
{
tin[u] = ++dfsTimer;
euler[dfsTimer] = u;
}
if (it[u] < sz(child[u]))
{
int v = child[u][it[u]++];
st.pb(v);
}
else
{
if (u) tout[u] = dfsTimer;
st.pop_back();
}
}
}
};
static KRT buildKRT(int N, const vector<vector<int>>& adj, bool isRight = false)
{
KRT krt(N);
vector<int> dsu(N + 1), active(N + 1, 0), stamp(N + 1, 0);
function<int(int)> find_set;
find_set = [&](int v) -> int
{
if (v == dsu[v]) return v;
return dsu[v] = find_set(dsu[v]);
};
int L = N, R = 1; if (isRight) swap(L, R);
FOR(i, L, R)
{
active[i] = 1;
dsu[i] = i;
vector<int> reps;
for (int j : adj[i]) if (active[j])
{
int r = find_set(j);
if (r == i) continue;
if (stamp[r] != i)
{
stamp[r] = i;
reps.pb(r);
}
}
for (int r : reps)
{
krt.child[i].pb(r);
krt.parent[r] = i;
}
for (int r : reps) dsu[r] = i;
}
FOR(v, 1, N)
{
int r = find_set(v);
if (r == v && !krt.parent[v])
{
krt.child[0].push_back(v);
krt.parent[v] = 0;
}
}
krt.buildEuler();
krt.buildLift();
return krt;
}
static int lift(const KRT& krt, int u, int threshold, bool isRight)
{
FOR(k, krt.LG - 1, 0)
{
int a = krt.up[k][u];
if (a != 0 && (a == threshold || ((a < threshold) == isRight))) u = a;
}
return u;
}
std::vector<int> check_validity(int N, std::vector<int> X, std::vector<int> Y,
std::vector<int> S, std::vector<int> E,
std::vector<int> L, std::vector<int> R)
{
int M = sz(X);
int Q = sz(S);
int mx = -1;
auto updateMax = [&](const vector<int>& a) { for (int v : a) mx = max(mx, v); };
updateMax(X); updateMax(Y);
updateMax(S); updateMax(E);
updateMax(L); updateMax(R);
if (mx <= N - 1)
{
for (int& v : X) ++v; for (int& v : Y) ++v;
for (int& v : S) ++v; for (int& v : E) ++v;
for (int& v : L) ++v; for (int& v : R) ++v;
}
vector<vector<int>> adj(N + 1);
FOR(i, 0, M - 1)
{
int a = X[i], b = Y[i];
adj[a].pb(b);
adj[b].pb(a);
}
KRT lef = buildKRT(N, adj, false);
KRT rig = buildKRT(N, adj, true);
vector<int> BIT(N + 1, 0);
auto add = [&](int pos) -> void { for (; pos <= N; pos += pos & (-pos)) ++BIT[pos]; };
auto sum = [&](int pos) -> int { int ret = 0; for (; pos > 0; pos -= pos & (-pos)) ret += BIT[pos]; return ret; };
auto query = [&](int l, int r) -> int
{
if (l > r) return 0;
return sum(r) - sum(l - 1);
};
vector<vector<int>> eventL(N + 1), eventR(N + 1);
vector<int> l1(Q, 0), r1(Q, -1), l2(Q, 0), r2(Q, -1);
vector<int> ans(Q, 0);
FOR(i, 0, Q - 1)
{
int s = S[i], e = E[i], l = L[i], r = R[i];
if (s < l || e > r) { ans[i] = 0; continue; }
int u = lift(lef, s, l, false);
int v = lift(rig, e, r, true);
l1[i] = lef.tin[u]; r1[i] = lef.tout[u];
l2[i] = rig.tin[v]; r2[i] = rig.tout[v];
eventR[r2[i]].pb(i);
eventL[l2[i] - 1].pb(i);
}
FOR(t, 0, N)
{
if (t >= 1)
{
int x = rig.euler[t];
add(lef.tin[x]);
}
for (int id : eventL[t]) ans[id] -= query(l1[id], r1[id]);
for (int id : eventR[t]) ans[id] += query(l1[id], r1[id]);
}
FOR(i, 0, Q - 1) ans[i] = (ans[i] > 0);
return ans;
}
