#include "werewolf.h"
#include <bits/stdc++.h>
#define pii pair<int,int>
#define f first
#define s second
using namespace std;
const int mxn = 2e5 + 2;
struct reachability_tree {
int parent[mxn];
int sz[mxn];
int in[mxn],out[mxn],id[mxn];
int pc[mxn];
vector<int> g[mxn];
vector<int> w[mxn];
int T=0;
void init(int n) {
for(int i=0;i<=n;i++) {
parent[i] = i;
sz[i] = 1;
}
}
int findrep(int u) {
return parent[u] == u ? u : findrep(parent[u]);
}
void unite(int u,int v,int cst) {
u=findrep(u);
v=findrep(v);
if(u == v) return;
if(sz[u] > sz[v]) swap(u,v);
parent[u] = v;
sz[v] += sz[u];
g[v].push_back(u);
w[v].push_back(cst);
pc[u] = cst;
}
void dfs(int u) {
in[u] = ++T;
id[T] = u;
for(int v : g[u]) {
dfs(v);
}
out[u] = T;
}
pii range(int u, int tm,bool f) {
if(f)
while(parent[u] != u && pc[u] >= tm) u = parent[u];
else
while(parent[u] != u && pc[u] <= tm) u = parent[u];
int p;
if(f) {
p = upper_bound(w[u].begin(),w[u].end(),tm,[](int a,int b) {
return a > b;
}) - w[u].begin();
} else {
p = upper_bound(w[u].begin(),w[u].end(),tm) - w[u].begin();
}
if(p == 0) {
return {in[u], in[u]};
}
int v = g[u][p-1];
return {in[u],out[v]};
}
} hum,wlf ;
int U[2*mxn],V[2*mxn];
struct BIT
{
int bit[mxn];
void init() {
memset(bit,0,sizeof bit);
}
void update(int p,int v) {
if(p==0) return;
for(;p<mxn;p+=p&-p) bit[p] += v;
}
int query(int p) {
int r=0;
for(;p>0;p-=p&-p) r+=bit[p];
return r;
}
} bt;
struct Query {
int L1,R1,L2,R2;
int v;
int ind;
Query(int a,int b,int c,int d,int i) : L1(a),R1(b),L2(c),R2(d),ind(i) {};
};
vector<int> check_validity(int N, vector<int> X, vector<int> Y,vector<int> S, vector<int> E, vector<int> L, vector<int> R) {
int m = X.size();
for(int i = 0 ; i < m; i++) {
U[i] = min(X[i],Y[i]), V[i] = max(X[i],Y[i]);
}
vector<int> p1,p2;
for(int i = 0; i < m; i++) {
p1.push_back(i);
p2.push_back(i);
}
sort(p1.begin(),p1.end(),[](int a,int b) {
return U[a] > U[b];
});
sort(p2.begin(),p2.end(),[](int a,int b) {
return V[a] < V[b];
});
hum.init(N);
wlf.init(N);
int q = S.size();
vector<int> res(q);
for(int i : p1) {
hum.unite(U[i],V[i],U[i]);
}
for(int i : p2) {
wlf.unite(U[i],V[i],V[i]);
}
for(int i = 0; i < N;i++) {
if(hum.parent[i] == i) hum.dfs(i);
if(wlf.parent[i] == i) wlf.dfs(i);
}
vector<Query> Q;
vector<int> sp[mxn];
vector<int> ep[mxn];
for(int i = 0; i < q; i++) {
pii x = hum.range(S[i],L[i],true);
pii y = wlf.range(E[i],R[i],false);
Q.push_back(Query(x.f,x.s,y.f,y.s,i));
sp[x.f].push_back(i);
ep[x.s].push_back(i);
}
bt.init();
for(int i = 1 ; i <= N; i++ ) {
for(int j : sp[i]) {
Q[j].v = bt.query(Q[j].R2) - bt.query(Q[j].L2 - 1);
}
bt.update(wlf.in[hum.id[i]],1);
for(int j : ep[i]) {
int t = bt.query(Q[j].R2) - bt.query(Q[j].L2 - 1);
if(t > Q[j].v)
res[j] = 1;
}
}
return res;
}
