#include "werewolf.h"
#include "bits/stdc++.h"
using namespace std;
const int LOG = 20;
const int MAX_N = 4e5 + 5;
int n[2];
int p[MAX_N][2];
int val[MAX_N][2];
vector<int> adj[MAX_N], g[MAX_N][2];
int get(int v, int ver) {
return p[v][ver] = (p[v][ver] == v ? v : get(p[v][ver], ver));
}
void unite(int u, int v, int ver) {
u = get(u, ver), v = get(v, ver);
if (u == v) return;
int puv = n[ver]++;
g[puv][ver].push_back(u);
g[puv][ver].push_back(v);
p[puv][ver] = p[u][ver] = p[v][ver] = puv;
if (ver == 0) {
val[puv][ver] = min(val[u][ver], val[v][ver]);
} else {
val[puv][ver] = max(val[u][ver], val[v][ver]);
}
}
int cnt[2];
int dep[MAX_N][2], up[MAX_N][2][LOG];
int lx[MAX_N][2], rx[MAX_N][2], owner[MAX_N][2];
void dfs(int v, int ver) {
lx[v][ver] = ++cnt[ver];
owner[cnt[ver]][ver] = v;
for (int u : g[v][ver]) {
dep[u][ver] = dep[v][ver] + 1;
up[u][ver][0] = v;
for (int j = 1; j < LOG; ++j) {
up[u][ver][j] = up[up[u][ver][j - 1]][ver][j - 1];
}
dfs(u, ver);
}
rx[v][ver] = cnt[ver];
}
int tree[MAX_N];
int common[MAX_N];
vector<array<int, 4>> qs[MAX_N];
void upd(int i) {
while (i < MAX_N) {
tree[i]++;
i += i & -i;
}
}
int query(int i) {
int ret = 0;
while (i) {
ret += tree[i];
i -= i & -i;
}
return ret;
}
int query(int l, int r) {
return query(r) - query(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 < (int) X.size(); ++i) {
adj[X[i]].push_back(Y[i]);
adj[Y[i]].push_back(X[i]);
}
n[0] = n[1] = N;
for (int i = 0; i < N; ++i) {
p[i][0] = p[i][1] = val[i][0] = val[i][1] = i;
}
for (int v = N - 1; v >= 0; --v) {
for (int u : adj[v]) {
if (u > v) {
unite(u, v, 0);
}
}
}
for (int v = 0; v < N; ++v) {
for (int u : adj[v]) {
if (u < v) {
unite(u, v, 1);
}
}
}
assert(n[0] == n[1] && n[0] == N * 2 - 1);
dfs(n[0] - 1, 0); dfs(n[1] - 1, 1);
int Q = (int) S.size();
for (int i = 0; i < Q; ++i) {
if (S[i] < L[i] || E[i] > R[i]) continue;
vector<int> r = {S[i], E[i]};
for (int j = LOG - 1; j >= 0; --j) {
if ((1 << j) <= dep[r[0]][0] && val[up[r[0]][0][j]][0] >= L[i]) {
r[0] = up[r[0]][0][j];
}
if ((1 << j) <= dep[r[1]][1] && up[r[1]][1][j] && val[up[r[1]][1][j]][1] <= R[i]) {
r[1] = up[r[1]][1][j];
}
}
int l1 = lx[r[0]][0], r1 = rx[r[0]][0];
int l2 = lx[r[1]][1], r2 = rx[r[1]][1];
qs[l2 - 1].push_back({l1, r1, -1, i});
qs[r2].push_back({l1, r1, 1, i});
}
for (int i = 1; i <= n[1]; ++i) {//eulerian
if (owner[i][1] < N) {
upd(lx[owner[i][1]][0]);
}
for (auto [l1, r1, v, j] : qs[i]) {
common[j] += query(l1, r1) * v;
}
}
vector<int> A(Q);
for (int i = 0; i < Q; ++i) {
A[i] = common[i] > 0;
}
return A;
}
