#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(i); } } 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; }