#include "bits/stdc++.h"
#include "werewolf.h"
using namespace std;
struct node
{
int mn, mx;
node()
{
mn = 1e9;
mx = 0;
}
};
node merge(node a, node b)
{
node c;
c.mx = max(a.mx, b.mx);
c.mn = min(a.mn, b.mn);
return c;
}
int n;
vector<node> t(8e5);
void upd(int pos, int x, int l = 0, int r = n - 1, int i = 1)
{
if (l == r)
t[i].mx = t[i].mn = x;
else
{
int m = (l + r) / 2;
if (pos <= m)
upd(pos, x, l, m, i * 2);
else
upd(pos, x, m + 1, r, i * 2 + 1);
t[i] = merge(t[i * 2], t[i * 2 + 1]);
}
}
node get(int l, int r, int tl = 0, int tr = n - 1, int i = 1)
{
if (l > tr || tl > r)
return t[0];
if (l <= tl && tr <= r)
return t[i];
int m = (tl + tr) / 2;
return merge(get(l, r, tl, m, i * 2), get(l, r, m + 1, tr, i * 2 + 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)
{
vector<int> vis(N), p, ind(N), ans(L.size());
vector<vector<int>> g(N);
int i;
n = N;
for (int i = 0; i < X.size(); i++)
g[X[i]].push_back(Y[i]);
for (int i = 0; i < X.size(); i++)
g[Y[i]].push_back(X[i]);
int start = 0;
while (g[start].size() != 1)
start++;
auto dfs = [&](auto dfs, int node, int par) -> void
{
p.push_back(node);
for (auto &x : g[node])
if (x != par)
dfs(dfs, x, node);
};
dfs(dfs, start, -1);
for (int i = 0; i < N; i++)
upd(i, p[i]), ind[p[i]] = i;
for (int i = 0; i < S.size(); i++)
{
S[i] = ind[S[i]];
E[i] = ind[E[i]];
int l = S[i];
int r = E[i];
if (l <= r)
{
int last_big = -1, first_small = -1;
while (l <= r)
{
int m = (l + r) / 2;
if (get(m, E[i]).mx > R[i])
last_big = m, l = m + 1;
else
r = m - 1;
}
l = S[i], r = E[i];
if (last_big == -1)
break;
while (l <= r)
{
int m = (l + r) / 2;
if (get(S[i], m).mn < L[i])
first_small = m, r = m - 1;
else
l = m + 1;
}
if (first_small == -1)
break;
if (last_big < first_small - 1)
{
ans[i] = 1;
}
}
else
{
swap(l, r);
int last_small = -1, first_big = -1;
while (l <= r)
{
int m = (l + r) / 2;
if (get(m, S[i]).mn < L[i])
last_small = m, l = m + 1;
else
r = m - 1;
}
l = E[i], r = S[i];
if (last_small == -1)
break;
while (l <= r)
{
int m = (l + r) / 2;
if (get(E[i], m).mx > R[i])
first_big = m, r = m - 1;
else
l = m + 1;
}
if (first_big == -1)
break;
if (last_small < first_big - 1)
ans[i] = 1;
}
}
return ans;
}
