#include <bits/stdc++.h>
#include "werewolf.h"
using namespace std;
#define dbg(x) cerr << #x << ": " << x << endl;
struct DSU {
vector<int> parent;
vector<vector<int>> tree;
vector<vector<int>> binup;
vector<int> tin;
vector<int> tout;
vector<int> vertices;
int n;
int max_k;
int timer;
DSU(int _n) : n(_n) {
parent.resize(n);
iota(parent.begin(), parent.end(), 0);
tree.resize(n);
tin.resize(n);
tout.resize(n);
vertices.resize(n);
timer = 0;
max_k = __lg(n) + 2;
binup.assign(max_k, vector<int>(n));
}
int find(int v) {
if (parent[v] == v) {
return v;
} else {
return parent[v] = find(parent[v]);
}
}
void unite(int u, int v) {
u = find(u);
assert(parent[v] == v);
if (u == v) return;
tree[v].push_back(u);
parent[u] = v;
}
void dfs(int v) {
vertices[timer] = v;
tin[v] = timer++;
for (auto u : tree[v]) {
binup[0][u] = v;
for (int k = 1; k < max_k; ++k) {
binup[k][u] = binup[k - 1][binup[k - 1][u]];
}
dfs(u);
}
tout[v] = timer - 1;
}
void traverse() {
for (int v = 0; v < n; ++v) {
if (parent[v] == v) {
for (int k = 0; k < max_k; ++k) {
binup[k][v] = v;
}
dfs(v);
}
}
}
};
struct Query {
static const int BLOCK_SIZE = 450;
int l;
int r;
int idx;
int block;
Query(int _l = 0, int _r = 0, int _idx = 0) : l(_l), r(_r), idx(_idx) {
block = l / BLOCK_SIZE;
}
bool operator<(const Query& other) const {
return tie(block, r) < tie(other.block, other.r);
}
};
struct FenwickTree {
vector<int> tree;
int n;
FenwickTree(int _n) : n(_n) {
tree.resize(n);
}
void update(int pos, int value) {
for (int i = pos; i < n; i |= i + 1) {
tree[i] += value;
}
}
int query(int l, int r) {
int res = 0;
for (int i = r; i >= 0; i = (i & (i + 1)) - 1) {
res += tree[i];
}
for (int i = l - 1; i >= 0; i = (i & (i + 1)) - 1) {
res -= tree[i];
}
return res;
}
};
vector<int> check_validity(int n, vector<int> x, vector<int> y, vector<int> s, vector<int> f, vector<int> ls, vector<int> rs) {
vector<vector<int>> g(n);
int m = x.size();
for (int i = 0; i < m; ++i) {
int u = x[i];
int v = y[i];
g[u].push_back(v);
g[v].push_back(u);
}
DSU dsu_right(n);
for (int v = 0; v < n; ++v) {
for (auto u : g[v]) {
if (u > v) continue;
dsu_right.unite(u, v);
}
}
DSU dsu_left(n);
for (int v = n - 1; v >= 0; --v) {
for (auto u : g[v]) {
if (u < v) continue;
dsu_left.unite(u, v);
}
}
dsu_right.traverse();
dsu_left.traverse();
int q = s.size();
vector<int> ans(q);
vector<Query> queries(q);
for (int i = 0; i < q; ++i) {
int v = f[i];
for (int k = dsu_right.max_k - 1; k >= 0; --k) {
if (dsu_right.binup[k][v] < rs[i]) {
v = dsu_right.binup[k][v];
}
}
if (dsu_right.binup[0][v] <= rs[i]) v = dsu_right.binup[0][v];
queries[i] = Query(dsu_right.tin[v], dsu_right.tout[v], i);
}
sort(queries.begin(), queries.end());
FenwickTree fenwick(n);
auto move_borders = [&](int& curr_l, int& curr_r, int l, int r) {
while (curr_l > l) {
--curr_l;
int v = dsu_right.vertices[curr_l];
fenwick.update(dsu_left.tin[v], 1);
}
while (curr_r < r) {
++curr_r;
int v = dsu_right.vertices[curr_r];
fenwick.update(dsu_left.tin[v], 1);
}
while (curr_l < l) {
int v = dsu_right.vertices[curr_l];
fenwick.update(dsu_left.tin[v], -1);
++curr_l;
}
while (curr_r > r) {
int v = dsu_right.vertices[curr_r];
fenwick.update(dsu_left.tin[v], -1);
--curr_r;
}
};
int curr_l = 0;
int curr_r = -1;
for (const auto& [l, r, idx, block] : queries) {
move_borders(curr_l, curr_r, l, r);
int v = s[idx];
for (int k = dsu_left.max_k - 1; k >= 0; --k) {
if (dsu_left.binup[k][v] > ls[idx]) {
v = dsu_left.binup[k][v];
}
}
if (dsu_left.binup[0][v] >= ls[idx]) v = dsu_left.binup[0][v];
if (fenwick.query(dsu_left.tin[v], dsu_left.tout[v]) > 0) {
ans[idx] = 1;
}
}
return ans;
}
