#include "werewolf.h"
#include <iostream>
using namespace std;
#define pb push_back
#define F first
#define S second
const int N = 200200;
int n;
vector<int> g[N];
vector<pair<pair<int, int>, pair<int, int>>> p[N];
struct tree {
int t[N << 2];
void upd(int pos, int val, int v = 1, int tl = 1, int tr = n) {
if (tl == tr)
return t[v] = val, void();
int tm = tl + tr >> 1;
if (pos <= tm)
upd(pos, val, v * 2, tl, tm);
else
upd(pos, val, v * 2 + 1, tm + 1, tr);
t[v] = max(t[v * 2], t[v * 2 + 1]);
}
int get(int l, int r, int v = 1, int tl = 1, int tr = n) {
if (l <= tl && tr <= r)
return t[v];
if (r < tl || tr < l)
return 0;
int tm = tl + tr >> 1;
return max(get(l, r, v * 2, tl, tm), get(l, r, v * 2 + 1, tm + 1, tr));
}
} t;
struct tree_dsu {
int p[N], sz[N], root, up[20][N], LG = 18;
int tin[N], tout[N], tick, pos[N];
vector<int> h[N];
int mxup(int v, int k) {
if (v == k) return v;
for (int i = LG; i >= 0; --i) {
int u = up[i][v];
if (u >= 0 && u >= k)
v = u;
}
return v;
}
int mnup(int v, int k) {
if (v == k) return v;
for (int i = LG; i >= 0; --i) {
int u = up[i][v];
if (u >= 0 && u <= k)
v = u;
}
return v;
}
void dfs(int v, int p = -1) {
tin[v] = ++tick;
pos[tick] = v;
up[0][v] = p;
for (int i = 1; i <= LG; ++i) {
if (up[i - 1][v] == -1)
up[i][v] = -1;
else
up[i][v] = up[i - 1][up[i - 1][v]];
}
for (auto to : h[v])
dfs(to, v);
tout[v] = tick;
}
void init(int n) {
for (int i = 0; i < n; ++i)
p[i] = i, sz[i] = 1, h[i].clear();
}
int get(int v) {
return p[v] = (v == p[v] ? v : get(p[v]));
}
void unite(int v, int u) {
if ((v = get(v)) == (u = get(u)))
return;
h[v].pb(u);
root = v;
sz[v] += sz[u];
p[u] = v;
}
} ds, sd;
vector<int> check_validity(int _n, vector<int> U, vector<int> V, vector<int> S, vector<int> E, vector<int> L, vector<int> R) {
int q = S.size();
int m = U.size();
n = _n;
int r;
vector<int> ans(q, 0);
ds.init(n);
sd.init(n);
for (int i = 0; i < m; ++i) {
g[U[i]].pb(V[i]);
g[V[i]].pb(U[i]);
}
for (int i = n - 1; i >= 0; --i) {
for (auto to : g[i]) {
if (to > i)
ds.unite(i, to);
}
}
for (int i = 0; i < n; ++i) {
for (auto to : g[i]) {
if (to < i)
sd.unite(i, to);
}
}
ds.dfs(ds.root);
sd.dfs(sd.root);
for (int i = 0, l1, r1, l2, r2, v, u; i < q; ++i) {
v = ds.mxup(S[i], L[i]);
u = sd.mnup(E[i], R[i]);
l1 = ds.tin[v], r1 = ds.tout[v];
l2 = sd.tin[u], r2 = sd.tout[u];
p[r1].pb({{i, l1}, {l2, r2}});
}
for (int i = 1; i <= n; ++i) {
t.upd(sd.tin[ds.pos[i]], i);
for (auto it : p[i]) {
if (t.get(it.S.F, it.S.S) >= it.F.S)
ans[it.F.F] = 1;
else
ans[it.F.F] = 0;
}
}
return ans;
}
