#include "werewolf.h"
#include <bits/stdc++.h>
#define pb push_back
#define x first
#define y second
#define all(a) a.begin(), a.end()
#define sz(a) (int)a.size()
#define rd() abs((int)rng())
using namespace std;
typedef long long ll;
typedef long double ld;
typedef pair<int, int> pii;
const int maxn = 2e5 + 100;
const int mod = 1e9 + 7;
mt19937 rng(chrono::high_resolution_clock::now().time_since_epoch().count());
vector<int>g[maxn];
int par[maxn];
int root(int v)
{
return v == par[v] ? v : par[v] = root(par[v]);
}
struct tree
{
int tin[maxn], tout[maxn], tim, anc[maxn][20], to_v[maxn];
vector<int>adj[maxn];
tree() = default;
void add_edge(int fr, int to)
{
adj[fr].pb(to);
}
void dfs(int v)
{
tin[v] = ++tim;
to_v[tim] = v;
for(int i = 1; i < 20; i++)
anc[v][i] = anc[anc[v][i - 1]][i - 1];
for(int to : adj[v])
{
anc[to][0] = v;
dfs(to);
}
tout[v] = tim;
}
} man, wolf;
int f[maxn];
void add(int i)
{
for(; i < maxn; i += i & -i)
f[i]++;
}
int get(int i)
{
int ret = 0;
for(; i > 0; i -= i & -i)
ret += f[i];
return ret;
}
int get(int l, int r)
{
return get(r) - get(l - 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)
{
for(int i = 0; i < sz(S); i++)
++S[i], ++E[i], ++L[i], ++R[i];
for(int i = 0; i < sz(X); i++)
{
++X[i], ++Y[i];
g[X[i]].pb(Y[i]);
g[Y[i]].pb(X[i]);
}
for(int i = 1; i <= n; i++)
par[i] = i;
for(int i = 1; i <= n; i++)
{
for(int to : g[i])
{
if(to < i && root(to) != i)
{
wolf.add_edge(i, root(to));
par[root(to)] = i;
}
}
}
for(int i = 1; i <= n; i++)
par[i] = i;
for(int i = n; i >= 1; i--)
{
for(int to : g[i])
{
if(to > i && root(to) != i)
{
man.add_edge(i, root(to));
par[root(to)] = i;
}
}
}
man.dfs(1);
wolf.dfs(n);
for(int i = 0; i < sz(S); i++)
{
int v = S[i];
for(int j = 19; j >= 0; j--)
{
if(man.anc[v][j] != 0 && man.anc[v][j] >= L[i])
v = man.anc[v][j];
}
S[i] = v;
v = E[i];
for(int j = 19; j >= 0; j--)
{
if(wolf.anc[v][j] != 0 && wolf.anc[v][j] <= R[i])
v = wolf.anc[v][j];
}
E[i] = v;
}
vector<tuple<int, int, int, int> >que[n + 1];
vector<int>ans(sz(S));
for(int i = 0; i < sz(S); i++)
{
que[wolf.tin[E[i]] - 1].pb(make_tuple(i, -1, man.tin[S[i]], man.tout[S[i]]));
que[wolf.tout[E[i]]].pb(make_tuple(i, +1, man.tin[S[i]], man.tout[S[i]]));
}
for(int i = 1; i <= n; i++)
{
add(man.tin[wolf.to_v[i]]);
for(auto aa : que[i])
{
int id, delta, l, r;
tie(id, delta, l, r) = aa;
ans[id] += delta * get(l, r);
}
}
for(int i = 0; i < sz(ans); i++)
ans[i] = (ans[i] > 0);
return ans;
}
