#include "werewolf.h"
#include <bits/stdc++.h>
#define pb push_back
#define pii pair<int, int>
#define X first
#define Y second
#define ub upper_bound
#define lb lower_bound
using namespace std;
/*
- Make Reachability Tree by sorting indexes and DSU
- Subtree of Vertex includes all Vertices reachable from that vertex
- Connect new vertex to parent of new connections
- Then use binary lifting to find highest vertex in subtree with val <= to query
- Finally use euler tour pre/ post vals to find rectangle needed to be queried
- Offline + Fenwick Tree to check if there is a vertex/point in rectangle
*/
struct disj{
vector<int> par;
disj(int n){
for(int i = 0; i<n; i++)par.pb(i);
}
int fi(int a){return (a == par[a]) ? a : par[a] = fi(par[a]);}
void me(int a, int b){
a = fi(a);
b = fi(b);
par[b] = a;
}
};
struct ft{
vector<int> fen;
ft(int n){
fen.assign(n+1, 0);
}
int qer(int a){
a++;
int ans = 0;
for(; a > 0; a-=a&(-a))ans+=fen[a];
return ans;
}
void upd(int a, int b){
a++;
for(; a < fen.size(); a+=a&(-a))fen[a]+=b;
}
};
void print(vector<vector<int>>& g2){
int k = 0;
for(auto i : g2){
cout << k <<':';k++;
for(auto j : i){
cout << j << ' ';
}
cout << '\n';
}
}
void dfs(int v, int p, int& counter, vector<vector<int>>& g, vector<vector<int>>& up, vector<pii>& time){
up[v][0] = p;
time[v].X = counter++;
for(int i = 1; i < 30; i++){
up[v][i] = up[up[v][i-1]][i-1];
}
for(auto ch : g[v])dfs(ch, v, counter, g, up, time);
time[v].Y = counter++;
}
int jump1(int v, int val, vector<vector<int>>& up){
for(int i = 29; i >= 0; i--){
if(up[v][i] <= val){
v = up[v][i];
}
}
return v;
}
int jump2(int v, int val, vector<vector<int>>& up){
for(int i = 29; i >= 0; i--){
if(up[v][i] >= val){
v = up[v][i];
}
}
return v;
}
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 Q = S.size(); int M = X.size();
vector<vector<int>> g;
g.assign(N, vector<int>());
for(int i = 0; i<M; i++){
g[X[i]].pb(Y[i]);
g[Y[i]].pb(X[i]);
}
disj sml(N), big(N);
vector<vector<int>> g1, g2, up1, up2;
vector<pii> time1, time2;
g1.assign(N, vector<int>());
g2.assign(N, vector<int>());
up1.assign(N, vector<int>(30));
up2.assign(N, vector<int>(30));
time1.assign(N, {0, 0});
time2.assign(N, {0, 0});
for(int i = 0; i < N; i++){
for(auto j : g[i]){
if(j < i && big.fi(i) != big.fi(j)){
g1[i].pb(big.fi(j));
big.me(i, j);
}
}
}
for(int i = N-1; i >= 0; i--){
for(auto j : g[i]){
if(j > i && sml.fi(i) != sml.fi(j)){
g2[i].pb(sml.fi(j));
sml.me(i, j);
}
}
}
int counter = 0;
dfs(N-1, N-1, counter, g1, up1, time1);counter = 0;
dfs(0, 0, counter, g2, up2, time2);
vector<vector<int>> events;
for(int i = 0; i< N; i++){
events.pb({time1[i].X, 0, time2[i].X, -1, -1});
}
for(int i = 0; i< Q; i++){
int tmp1 = jump1(E[i], R[i], up1);
int tmp2 = jump2(S[i], L[i], up2);
events.pb({time1[tmp1].X, -1, time2[tmp2].X, time2[tmp2].Y, i});
events.pb({time1[tmp1].Y, 1, time2[tmp2].X, time2[tmp2].Y, i});
}
//print(events);
sort(events.begin(), events.end());
ft fen(2*N+5);
vector<int> A(Q);
for(auto i : events){
if(i[1] == 0){
fen.upd(i[2], 1);
}else{
int ans = fen.qer(i[3])-fen.qer(i[2]-1);
A[i[4]] += ans*i[1];
}
}
//for(auto i : A)cout << i << ' ';
for (int i = 0; i < Q; ++i){
if(A[i]>0)A[i] = 1;
}
return A;
}
