#include "werewolf.h"
#include <bits/stdc++.h>
using namespace std;
#define all(v) (v).begin(), (v).end()
#define rall(v) (v).rbegin(), (v).rend()
using VI = vector<int>;
const int maxn = 4e5 + 5;
int N, M, Q;
int U[maxn], V[maxn];
namespace pre {
int parent[maxn];
vector<int> g[maxn], w[maxn];
int sz[maxn], par[maxn], pw[maxn];
int in[maxn], tour[maxn];
int tym = 0;
void init() {
for(int i = 0; i < N; i++) {
sz[i] = 1, par[i] = i;
}
}
int find(int u) {
return par[u] == u ? u : find(par[u]);
}
void join(int u, int v) {
int weight = max(u, v);
u = find(u), v = find(v);
if(u == v) return;
if(sz[u] > sz[v]) swap(u, v);
par[u] = v, pw[u] = weight;
sz[v] += sz[u];
g[v].emplace_back(u);
w[v].emplace_back(weight);
}
void dfs(int u) {
tour[tym] = u;
in[u] = tym++;
for(int v : g[u]) {
dfs(v);
}
}
pair<int, int> range(int u, int weight) {
while(par[u] != u and pw[u] <= weight)
u = par[u];
if(sz[u] == 1) // leaf
return {in[u], in[u]};
int it = upper_bound(all(w[u]), weight) - w[u].begin();
if(it == 0) // can't go nowhere
return {in[u], in[u]};
int v = g[u][it - 1];
return {in[u], in[v] + sz[v] - 1};
}
}
namespace suf {
int parent[maxn];
vector<int> g[maxn], w[maxn];
int sz[maxn], par[maxn], pw[maxn];
int in[maxn], tour[maxn];
int tym = 0;
void init() {
for(int i = 0; i < N; i++) {
sz[i] = 1, par[i] = i;
}
}
int find(int u) {
return par[u] == u ? u : find(par[u]);
}
void join(int u, int v) {
int weight = min(u, v);
u = find(u), v = find(v);
if(u == v) return;
if(sz[u] > sz[v]) swap(u, v);
par[u] = v, pw[u] = weight;
sz[v] += sz[u];
g[v].emplace_back(u);
w[v].emplace_back(weight);
}
void dfs(int u) {
tour[tym] = u;
in[u] = tym++;
for(int v : g[u]) {
dfs(v);
}
}
pair<int, int> range(int u, int weight) {
while(par[u] != u and pw[u] >= weight)
u = par[u];
if(sz[u] == 1) // leaf
return {in[u], in[u]};
int it = upper_bound(all(w[u]), weight, [](int x, int y){ return x > y; }) - w[u].begin();
if(it == 0) // can't go nowhere
return {in[u], in[u]};
int v = g[u][it - 1];
return {in[u], in[v] + sz[v] - 1};
}
}
vector<int> check_validity(int _N, VI X, VI Y, VI S, VI E, VI L, VI R) {
N = _N, M = X.size(), Q = S.size();
for(int i = 0; i < M; i++) {
U[i] = X[i], V[i] = Y[i];
if(U[i] > V[i]) swap(U[i], V[i]);
}
pre::init();
suf::init();
vector<int> p(M), q(M);
iota(p.begin(), p.end(), 0);
iota(q.begin(), q.end(), 0);
sort(p.begin(), p.end(), [](int x, int y){ return V[x] < V[y]; });
sort(q.begin(), q.end(), [](int x, int y){ return U[x] > U[y]; });
for(int i : p)
pre::join(U[i], V[i]);
for(int i : q)
suf::join(U[i], V[i]);
pre::dfs(pre::find(0));
suf::dfs(suf::find(0));
int tour[maxn], index[maxn];
for(int i = 0; i < N; i++) {
index[pre::tour[i]] = i;
}
for(int i = 0; i < N; i++) {
tour[i] = index[suf::tour[i]];
}
vector<int> ans(Q);
struct data {
int L, id, op, l, r;
data() {}
data(int _L, int _id, int _op, int _l, int _r) {
L = _L, id = _id, op = _op, l = _l, r = _r;
}
bool operator < (const data &that) const {
return L < that.L;
}
};
vector<data> shit_load;
for(int i = 0; i < Q; i++) {
int l1, l2, r1, r2;
tie(l1, r1) = pre::range(E[i], R[i]);
tie(l2, r2) = suf::range(S[i], L[i]);
shit_load.push_back(data(r2, i, +1, l1, r1));
if(l2 != 0) shit_load.push_back(data(l2 - 1, i, -1, l1, r1));
}
int ft[maxn];
memset(ft, 0, sizeof ft);
auto update = [&](int i) {
i++;
for(; i < maxn; i += i & -i) ft[i]++;
};
auto query = [&](int l, int r) {
r++;
int ret = 0;
for(; l > 0; l -= l & -l) ret -= ft[l];
for(; r > 0; r -= r & -r) ret += ft[r];
return ret;
};
sort(all(shit_load));
int it = 0;
for(data e : shit_load) {
while(it < N and it <= e.L) {
update(tour[it]);
it++;
}
ans[e.id] += e.op * query(e.l, e.r);
}
for(int &i : ans) i = bool(i);
return ans;
}
