#include "werewolf.h"
#include <algorithm>
#include <utility>
namespace DSU
{
int fa[600005];
inline void init(int n) { for (int i = 0; i < n; i++) fa[i] = i; }
int getfa(int u) { return u == fa[u] ? u : fa[u] = getfa(fa[u]); }
}
struct Tree
{
int fa[600005][25], val[600005], st[600005], en[600005], clk;
std::vector<int> son[600005];
void dfs(int u, int f = -1)
{
fa[u][0] = f;
for (int i = 1; i < 20; i++)
fa[u][i] = fa[u][i - 1] == -1 ? -1 : fa[fa[u][i - 1]][i - 1];
st[u] = clk++;
for (int v : son[u])
dfs(v, u);
en[u] = clk - 1;
}
template <typename funcT>
inline void init(int n, std::vector<int> &eu, std::vector<int> &ev, funcT func)
{
int m = eu.size();
DSU::init(n + m);
std::vector<int> edge(m);
for (int i = 0; i < m; i++)
edge[i] = i;
std::sort(edge.begin(), edge.end(), [&] (int x, int y) { return func(x) > func(y); });
int cur = n;
for (int e : edge)
{
int u = DSU::getfa(eu[e]), v = DSU::getfa(ev[e]);
if (u == v)
continue;
DSU::fa[u] = DSU::fa[v] = cur;
son[cur].push_back(u);
son[cur].push_back(v);
val[cur++] = func(e);
}
dfs(cur - 1);
}
inline std::pair<int, int> query(int u, int x)
{
for (int i = 19; i >= 0; i--)
{
if (~fa[u][i] && val[fa[u][i]] >= x)
u = fa[u][i];
}
return {st[u], en[u]};
}
} human, werewolf;
int BIT[600005], LIM = 6e5 + 2;
inline void modify(int pos)
{
for (pos++; pos <= LIM; pos += pos & -pos)
BIT[pos]++;
}
inline int query(int pos)
{
int res = 0;
for (pos++; pos; pos -= pos & -pos)
res += BIT[pos];
return res;
}
std::vector<int> check_validity(int n, std::vector<int> eu, std::vector<int> ev,
std::vector<int> qu, std::vector<int> qv,
std::vector<int> ql, std::vector<int> qr)
{
int q = qu.size();
human.init(n, eu, ev, [&] (int x) { return std::min(eu[x], ev[x]); });
werewolf.init(n, eu, ev, [&] (int x) { return -std::max(eu[x], ev[x]); });
std::vector<std::vector<std::pair<int, int> > > vec(human.clk);
for (int i = 0; i < q; i++)
{
auto x = human.query(qu[i], ql[i]), y = werewolf.query(qv[i], -qr[i]);
int l = x.first, r = x.second, L = y.first, R = y.second;
vec[l].emplace_back(R, i);
if (L)
vec[l].emplace_back(L - 1, ~i);
if (r + 1 < human.clk)
{
vec[r + 1].emplace_back(R, ~i);
if (L)
vec[r + 1].emplace_back(L - 1, i);
}
}
std::vector<int> val(human.clk, -1), ans(q);
for (int i = 0; i < n; i++)
val[human.st[i]] = werewolf.st[i];
for (int i = human.clk - 1; i >= 0; i--)
{
if (~val[i])
modify(val[i]);
for (auto &it : vec[i])
{
int res = query(it.first), x = it.second;
if (x >= 0)
ans[x] += res;
else
ans[~x] -= res;
}
}
for (int i = 0; i < q; i++)
ans[i] = (bool)ans[i];
return ans;
}
