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