#include <iostream>
#include <vector>
#include <set>
#include <algorithm>
#include "werewolf.h"
using namespace std;
const int N = (1<<19) + 1;
set<int> Set[N<<1];
int nei[2][N][2];
vector<int> ans;
int Lft[2][N], Rgt[2][N], Par[2][N][20], par[2][N], Min[N][20], Max[N][20];
void insert(int x, int y, int cur = 1, int st = 1, int en = N){
if (x >= en or x < st)
return;
Set[cur].insert(y);
if (en - st == 1)
return;
int lc = cur + cur, rc = lc + 1, mid = (st + en) / 2;
insert(x, y, lc, st, mid);
insert(x, y, rc, mid, en);
}
int get(int x1, int x2, int y1, int y2, int cur = 1, int st = 1, int en = N){
if (x1 >= en or x2 <= st)
return 0;
if (x1 <= st and x2 >= en)
return Set[cur].upper_bound(y1 - 1) != Set[cur].upper_bound(y2 - 1);
int lc = cur + cur, rc = lc + 1, mid = (st + en) / 2;
return get(x1, x2, y1, y2, lc, st, mid) | get(x1, x2, y1, y2, rc, mid, en);
}
void dfs(int tp, int u, int p, int &vr){
// cout<<tp<<" "<<p<<" --> "<<u<<endl;
Lft[tp][u] = vr;
Par[tp][u][0] = p;
for (int i=1;i<=18;i++){
Par[tp][u][i] = (Par[tp][u][i-1] == -1 ? -1 : Par[tp][Par[tp][u][i-1]][i-1]);
if (tp == 0)
Max[u][i] = max(Max[u][i-1], (Par[tp][u][i-1] == -1 ? N : Max[Par[tp][u][i-1]][i-1]));
else
Min[u][i] = min(Min[u][i-1], (Par[tp][u][i-1] == -1 ? -1 : Min[Par[tp][u][i-1]][i-1]));
}
if (nei[tp][u][0] + nei[tp][u][1] == 0){
vr++;
}
else{
dfs(tp, nei[tp][u][0], u, vr);
dfs(tp, nei[tp][u][1], u, vr);
}
Rgt[tp][u] = vr - 1;
}
int root(int tp, int v){
return (par[tp][v] == 0 or par[tp][v] == v ? v : par[tp][v] = root(tp, par[tp][v]));
}
vector<int> check_validity(int n, vector<int> U, vector<int> V, vector<int> X, vector<int> Y, vector<int> L, vector<int> R){
int m = U.size(), q = L.size(), it1 = n - 1, it2 = n - 1, vr = 2;
vector<pair<int,int>> E1, E2;
for (int i=0;i<m;i++){
E1.push_back({max(U[i], V[i]), i});
E2.push_back({min(U[i], V[i]), i});
}
sort(begin(E1), end(E1));
sort(rbegin(E2), rend(E2));
for (auto [vl, id] : E1){
int A = root(0, U[id]), B = root(0, V[id]);
if (A == B)
continue;
par[0][A] = par[0][B] = ++it1;
Max[A][0] = Max[B][0] = vl;
nei[0][it1][0] = A;
nei[0][it1][1] = B;
}
for (auto [vl, id] : E2){
int A = root(1, U[id]), B = root(1, V[id]);
if (A == B)
continue;
par[1][A] = par[1][B] = ++it2;
Min[A][0] = Min[B][0] = vl;
nei[1][it2][0] = A;
nei[1][it2][1] = B;
}
dfs(0, it1, -1, vr);
vr = 2;
dfs(1, it2, -1, vr);
for (int i=0;i<n;i++)
insert(Lft[0][i], Lft[1][i]);
for (int Id=0;Id<q;Id++){
int B = X[Id], A = Y[Id];
for (int i=18;i>=0;i--){
if (Par[0][A][i] != -1 and Max[A][i] <= R[Id])
A = Par[0][A][i];
if (Par[1][B][i] != -1 and Min[B][i] >= L[Id])
B = Par[1][B][i];
}
ans.push_back(get(Lft[0][A], Rgt[0][A] + 1, Lft[1][B], Rgt[1][B] + 1));
}
return ans;
}
