#include "werewolf.h"
#include <bits/stdc++.h>
using namespace std;
struct SegTree2D{
int n;
vector<bool> cnt={false};
vector<vector<int>> child={{}};
vector<pair<pair<int,int>,pair<int,int>>> range={make_pair(make_pair(1,1),make_pair(1,1))};
void init(int N){
n=N;
range[0].second=make_pair(N,N);
}
void add(int id, int &x,int &y){
int lx=range[id].first.first,ly=range[id].first.second,rx=range[id].second.first,ry=range[id].second.second;
if(x<lx||x>rx||y<ly||y>ry){
return;
}else if(lx==rx&&ly==ry){
cnt[id]=true;
return;
}
if(child[id].size()==0){
int tmp=child.size(),mx=lx+(rx-lx)/2,my=ly+(ry-ly)/2;
for(int i=0;i<4;i++){
child[id].push_back(tmp+i);
child.push_back({});
cnt.push_back(false);
range.push_back(make_pair(make_pair(1,1),make_pair(0,0)));
}
range[child[id][0]]=make_pair(make_pair(lx,ly),make_pair(mx,my));
range[child[id][1]]=make_pair(make_pair(mx+1,ly),make_pair(rx,my));
range[child[id][2]]=make_pair(make_pair(lx,my+1),make_pair(mx,ry));
range[child[id][3]]=make_pair(make_pair(mx+1,my+1),make_pair(rx,ry));
}
for(int i=0;i<4;i++){
add(child[id][i],x,y);
cnt[id]=cnt[id]||cnt[child[id][i]];
}
}
bool query(int id,int &Lx,int &Ly,int &Rx,int &Ry){
int lx=range[id].first.first,ly=range[id].first.second,rx=range[id].second.first,ry=range[id].second.second;
// cout << id << ' ' << lx << ' ' << ly << ' ' << rx << ' ' << ry << ' ' << cnt[id] << '\n';
if(Rx<lx||Lx>rx||Ry<ly||Ly>ry){
return false;
}else if(lx>=Lx&&rx<=Rx&&ly>=Ly&&ry<=Ry){
return cnt[id];
}else if(!cnt[id]){
return cnt[id];
}
bool ans=false;
for(int i=0;i<4;i++){
ans=ans||query(child[id][i],Lx,Ly,Rx,Ry);
}
return ans;
}
};
int n;
vector<int> node_wolf,dsu,order_wolf,node_human,order_human;
vector<vector<int>> par_wolf,par_human;
vector<pair<int,int>> edge,child_wolf,bound_wolf,child_human,bound_human;
int find_root(int &u){
if(u==dsu[u]){
return u;
}
return dsu[u]=find_root(dsu[u]);
}
void dfs_wolf(int u){
for(int i=1;i<18;i++){
par_wolf[u][i]=par_wolf[par_wolf[u][i-1]][i-1];
}
if(u<n){
order_wolf.push_back(u);
bound_wolf[u]={order_wolf.size(),order_wolf.size()};
return;
}
dfs_wolf(child_wolf[u].first);
dfs_wolf(child_wolf[u].second);
bound_wolf[u]={bound_wolf[child_wolf[u].first].first,bound_wolf[child_wolf[u].second].second};
}
void dfs_human(int u){
for(int i=1;i<18;i++){
par_human[u][i]=par_human[par_human[u][i-1]][i-1];
}
if(u<n){
order_human.push_back(u);
bound_human[u]={order_human.size(),order_human.size()};
return;
}
dfs_human(child_human[u].first);
dfs_human(child_human[u].second);
bound_human[u]={bound_human[child_human[u].first].first,bound_human[child_human[u].second].second};
}
std::vector<int> check_validity(int N, std::vector<int> X, std::vector<int> Y,
std::vector<int> S, std::vector<int> E,
std::vector<int> L, std::vector<int> R) {
n=N;
int Q = S.size();
vector<int> A(Q);
edge.resize(X.size());
for(int i=0;i<X.size();i++){
edge[i]={max(X[i],Y[i]),min(X[i],Y[i])};
}
sort(edge.begin(),edge.end());
node_wolf.resize(N);par_wolf.resize(N);dsu.resize(N);child_wolf.resize(N);
for(int i=0;i<N;i++){
node_wolf[i]=i;
par_wolf[i].resize(18,i);
dsu[i]=i;
}
for(int i=0;i<edge.size();i++){
if(find_root(edge[i].first)!=find_root(edge[i].second)){
par_wolf[find_root(edge[i].first)][0]=node_wolf.size();
par_wolf[find_root(edge[i].second)][0]=node_wolf.size();
child_wolf.push_back({find_root(edge[i].first),find_root(edge[i].second)});
dsu[find_root(edge[i].first)]=dsu[find_root(edge[i].second)]=node_wolf.size();
node_wolf.push_back(edge[i].first);
par_wolf.push_back(vector<int>(18,par_wolf.size()));
dsu.push_back(dsu.size());
}
}
bound_wolf.resize(dsu.size());
dfs_wolf(bound_wolf.size()-1);
for(int i=0;i<X.size();i++){
edge[i]={min(X[i],Y[i]),max(X[i],Y[i])};
}
sort(edge.begin(),edge.end());
node_human.resize(N);par_human.resize(N);dsu.clear();dsu.resize(N);child_human.resize(N);
for(int i=0;i<N;i++){
node_human[i]=i;
par_human[i].resize(18,i);
dsu[i]=i;
}
for(int i=edge.size()-1;i>=0;i--){
if(find_root(edge[i].first)!=find_root(edge[i].second)){
par_human[find_root(edge[i].first)][0]=node_human.size();
par_human[find_root(edge[i].second)][0]=node_human.size();
child_human.push_back({find_root(edge[i].first),find_root(edge[i].second)});
dsu[find_root(edge[i].first)]=dsu[find_root(edge[i].second)]=node_human.size();
node_human.push_back(edge[i].first);
par_human.push_back(vector<int>(18,par_human.size()));
dsu.push_back(dsu.size());
}
}
bound_human.resize(dsu.size());
dfs_human(bound_human.size()-1);
SegTree2D ds;ds.init(N);
vector<pair<int,int>> coor;
coor.resize(order_human.size());
for(int i=0;i<order_human.size();i++){
coor[order_human[i]].first=i+1;
coor[order_wolf[i]].second=i+1;
}
for(int i=0;i<order_human.size();i++){
ds.add(0,coor[i].first,coor[i].second);
}
for(int i=0;i<Q;i++){
for(int j=17;j>=0;j--){
if(node_human[par_human[S[i]][j]]>=L[i]){
S[i]=par_human[S[i]][j];
}
if(node_wolf[par_wolf[E[i]][j]]<=R[i]){
E[i]=par_wolf[E[i]][j];
}
}
if(ds.query(0,bound_human[S[i]].first,bound_wolf[E[i]].first,bound_human[S[i]].second,bound_wolf[E[i]].second)){
A[i]=1;
}else{
A[i]=0;
}
}
return A;
}
//Nlog(N)
//Qlog(N)^2
