#include "werewolf.h"
#include <bits/stdc++.h>
using namespace std;
int N, M, Q;
vector<vector<int>> graph;
vector<int> human, wolf;
vector<vector<int>> treeWolf;
vector<vector<int>> treeHuman;
vector<pair<int, int>> prepostWolf;
vector<pair<int, int>> prepostHuman;
vector<vector<int>> jumpWolf;
vector<vector<int>> jumpHuman;
struct ufToMakeArrays {
vector<int> chefs;
void init() {
chefs.resize(N);
for (int i = 0; i<N; i++) {
chefs[i] = i;
}
}
int find(int x) {
if (chefs[x] == x) return x;
return chefs[x] = find(chefs[x]);
}
void unite(int a, int b, bool minmax) {
a = find(a);
b = find(b);
if (a == b) return;
if (minmax?a<b:a>b) swap(a, b);
chefs[b] = a;
}
void makeTreeWolf() {
init();
for (int i = 0; i<N; i++) {
for (int u: graph[i]) {
if (u >= i) continue;
if (find(u) == find(i)) continue;
treeWolf[find(i)].push_back(find(u));
treeWolf[find(u)].push_back(find(i));
unite(u, i, 1);
}
}
}
void makeTreeHuman() {
init();
for (int i = N-1; i>=0; i--) {
for (int u: graph[i]) {
if (u <= i) continue;
if (find(u) == find(i)) continue;
treeHuman[find(i)].push_back(find(u));
treeHuman[find(u)].push_back(find(i));
unite(u, i, 0);
}
}
}
void dfsWolf(int v, int p) {
jumpWolf[0][v] = p;
prepostWolf[v].first = wolf.size();
wolf.push_back(v);
for (int i: treeWolf[v]) {
if (i == p) continue;
dfsWolf(i, v);
}
prepostWolf[v].second = wolf.size()-1;
}
void dfsHuman(int v, int p) {
jumpHuman[0][v] = p;
prepostHuman[v].first = human.size();
human.push_back(v);
for (int i: treeHuman[v]) {
if (i == p) continue;
dfsHuman(i, v);
}
prepostHuman[v].second = human.size()-1;
}
void make() {
treeHuman.assign(N, vector<int>()); treeWolf.assign(N, vector<int>());
makeTreeWolf(); makeTreeHuman();
wolf.clear(); human.clear();
prepostHuman.assign(N, {0, 0});
prepostWolf.assign(N, {0, 0});
jumpHuman.assign(20, vector<int>(N));
jumpWolf.assign(20, vector<int>(N));
dfsWolf(N-1, -1); dfsHuman(0, -1);
for (int i = 1; i<20; i++) {
for (int j = 0; j<N; j++) {
jumpHuman[i][j] = jumpHuman[i-1][j] == -1 ? -1 : jumpHuman[i-1][jumpHuman[i-1][j]];
jumpWolf[i][j] = jumpWolf[i-1][j] == -1 ? -1 : jumpWolf[i-1][jumpWolf[i-1][j]];
}
}
}
};
vector<int> wolfInv, humanInv, humanToWolf;
void makeInv() {
wolfInv.resize(N);
humanInv.resize(N);
for (int i = 0; i<N; i++) wolfInv[wolf[i]] = i;
for (int i = 0; i<N; i++) humanInv[human[i]] = i;
humanToWolf.resize(N);
for (int i = 0; i<N; i++) humanToWolf[i] = wolfInv[human[i]];
}
struct seg {
struct node {
int val=0, left=-1, right=-1;
};
vector<node> tree = {node()};
void build(int v, int rl, int rr) {
if (rl == rr) return;
tree[v].left = tree.size();
tree.push_back(node());
tree[v].right = tree.size();
tree.push_back(node());
int rm = (rl + rr)/2;
build(tree[v].left, rl, rm);
build(tree[v].right, rm+1, rr);
}
int update(int v, int rl, int rr, int pos, int x) {
if (rl == rr) {
int newV = tree.size();
tree.push_back(tree[v]);
tree[newV].val += x;
return newV;
}
int rm = (rl + rr)/2;
int newV = tree.size();
tree.push_back(tree[v]);
if (pos <= rm) tree[newV].left = update(tree[newV].left, rl, rm, pos, x);
else tree[newV].right = update(tree[newV].right, rm+1, rr, pos, x);
tree[newV].val = tree[tree[newV].left].val + tree[tree[newV].right].val;
return newV;
}
int query(int v, int rl, int rr, int ql, int qr) {
if (ql > qr) return 0;
if (rl == ql && rr == qr) return tree[v].val;
int rm = (rl + rr)/2;
return query(tree[v].left, rl, rm, ql, min(qr, rm)) + query(tree[v].right, rm+1, rr, max(ql, rm+1), qr);
}
vector<int> times;
int queryDouble(int hl, int hr, int wl, int wr) {
// cerr << query(times[wr], 0, N-1, hl, hr) << " - " << query(times[wl-1], 0, N-1, hl, hr) << "\n";
// return query(times[wr], 0, N-1, hl, hr) - (wl==0?0:query(times[wl-1], 0, N-1, hl, hr));
return query(times[hr], 0, N-1, wl, wr) - (hl==0?0:query(times[hl-1], 0, N-1, wl, wr));
}
void init() {
build(0, 0, N-1);
for (int i = 0; i<N; i++) {
times.push_back(update(i==0?0:times.back(), 0, N-1, humanToWolf[i], 1));
}
assert((int)times.size() == N);
}
};
pair<int, int> getRangeHuman(int pos, int lim) {
for (int i = 19; i>=0; i--) {
if (jumpHuman[i][pos] != -1 && jumpHuman[i][pos] >= lim) {
pos = jumpHuman[i][pos];
}
}
return prepostHuman[pos];
}
pair<int, int> getRangeWolf(int pos, int lim) {
for (int i = 19; i>=0; i--) {
if (jumpWolf[i][pos] != -1 && jumpWolf[i][pos] <= lim) {
pos = jumpWolf[i][pos];
}
}
return prepostWolf[pos];
}
vector<int> check_validity(int _N, vector<int> X, vector<int> Y, vector<int> S, vector<int> E, vector<int> L, vector<int> R) {
N = _N;
M = X.size();
Q = S.size();
graph.clear();
graph.resize(N);
for (int i = 0; i<M; i++) {
graph[X[i]].push_back(Y[i]);
graph[Y[i]].push_back(X[i]);
}
ufToMakeArrays blub;
blub.make();
makeInv();
// for (int i: human) cerr << i << " ";
// cerr << "\n";
// for (int i: wolf) cerr << i << " ";
// cerr << "\n";
seg tree;
tree.init();
vector<int> res(Q, 0);
for (int i = 0; i<Q; i++) {
// cerr << humanInv[S[i]] << "\n";
pair<int, int> rangeHuman = getRangeHuman(S[i], L[i]);
pair<int, int> rangeWolf = getRangeWolf(E[i], R[i]);
// cerr << rangeHuman.first << " " << rangeHuman.second << " " << rangeWolf.first << " " << rangeWolf.second << "\n";
// cerr << tree.queryDouble(rangeHuman.first, rangeHuman.second, rangeWolf.first, rangeWolf.second) << "\n";
if (tree.queryDouble(rangeHuman.first, rangeHuman.second, rangeWolf.first, rangeWolf.second)) res[i] = 1;
}
return res;
}
