#include "werewolf.h"
#include <bits/stdc++.h>
using std::vector;
using std::array;
using std::pair;
using std::tuple;
template <class F> struct RecLambda : private F {
RecLambda(F&& f) : F(std::forward<F>(f)) {}
template <class... Args> decltype(auto) operator()(Args&&... args) const {
return F::operator()(*this, std::forward<Args>(args)...);
}
};
struct UnionFind {
vector<int> par;
vector<vector<int>> child;
UnionFind(const int n) : par(n, -1), child(n) {}
int find(const int u) {
return par[u] < 0 ? u : par[u] = find(par[u]);
}
int merge(int x, int y) {
x = find(x), y = find(y);
if (x == y) return x;
const int z = (int)par.size();
par.push_back(-1);
child.emplace_back();
par[x] = par[y] = z;
child[z].push_back(x);
child[z].push_back(y);
return z;
}
vector<pair<int, int>> order() const {
vector<pair<int, int>> ret(par.size());
int timer = 0;
RecLambda([&](auto&& dfs, const int u) -> void {
ret[u].first = timer;
if (child[u].empty()) {
timer += 1;
} else {
for (const int v : child[u]) {
dfs(v);
}
}
ret[u].second = timer;
})((int)par.size() - 1);
return ret;
}
};
struct Fenwick {
vector<int> data;
Fenwick(const int n) : data(n + 1) {}
void add(int x) {
x += 1;
while (x < (int)data.size()) {
data[x] += 1;
x += x & -x;
}
}
int pref(int x) const {
int ret = 0;
while (x > 0) {
ret += data[x];
x -= x & -x;
}
return ret;
}
int fold(const int l, const int r) const {
return pref(r) - pref(l);
}
};
vector<int> check_validity(int N, vector<int> X, vector<int> Y, vector<int> S, vector<int> E, vector<int> L, vector<int> R) {
const int M = (int)X.size();
const int Q = (int)S.size();
vector<vector<int>> graph(N);
for (int i = 0; i < M; ++i) {
graph[X[i]].push_back(Y[i]);
graph[Y[i]].push_back(X[i]);
}
vector<int> xl(Q), xr(Q);
vector<int> x(N);
{
vector<vector<int>> list(N);
for (int i = 0; i < Q; ++i) {
list[L[i]].push_back(i);
}
UnionFind human(N);
vector<int> memo(Q);
for (int i = N - 1; i >= 0; --i) {
for (const int j : graph[i]) {
if (j >= i) {
human.merge(i, j);
}
}
for (const int j : list[i]) {
memo[j] = human.find(S[j]);
}
}
const auto vec = human.order();
for (int i = 0; i < N; ++i) {
x[i] = vec[i].first;
}
for (int i = 0; i < Q; ++i) {
xl[i] = vec[memo[i]].first;
xr[i] = vec[memo[i]].second;
}
}
vector<int> yl(Q), yr(Q);
vector<int> y(N);
{
vector<vector<int>> list(N);
for (int i = 0; i < Q; ++i) {
list[R[i]].push_back(i);
}
UnionFind wolf(N);
vector<int> memo(Q);
for (int i = 0; i < N; ++i) {
for (const int j : graph[i]) {
if (j <= i) {
wolf.merge(i, j);
}
}
for (const int j : list[i]) {
memo[j] = wolf.find(E[j]);
}
}
const auto vec = wolf.order();
for (int i = 0; i < N; ++i) {
y[i] = vec[i].first;
}
for (int i = 0; i < Q; ++i) {
yl[i] = vec[memo[i]].first;
yr[i] = vec[memo[i]].second;
}
}
vector<int> add(N);
for (int i = 0; i < N; ++i) {
add[x[i]] = y[i];
}
vector<int> count(Q);
vector<vector<int>> start(N), end(N);
for (int i = 0; i < Q; ++i) {
start[xl[i]].push_back(i);
end[xr[i] - 1].push_back(i);
}
Fenwick fen(N);
for (int x = 0; x < N; ++x) {
for (const int i : start[x]) {
count[i] -= fen.fold(yl[i], yr[i]);
}
fen.add(add[x]);
for (const int i : end[x]) {
count[i] += fen.fold(yl[i], yr[i]);
}
}
for (auto& x : count) {
x = x > 0;
}
return count;
}
