#include "werewolf.h"
#include <bits/stdc++.h>
using namespace std;
vector< int > v;
struct node{
node* l, *r;
int mini, maxi;
void update(){
mini = INT_MAX;
maxi = INT_MIN;
if(l){
mini = min(mini, l->mini);
maxi = max(maxi, l->maxi);
}
if(r){
mini = min(mini, r->mini);
maxi = max(maxi, r->maxi);
}
}
};
void Build(node* root, int left, int right){
if(left == right){
root->mini = root->maxi = v[left];
return;
}
root->l = new node{NULL,NULL,0,0};
root->r = new node{NULL,NULL,0,0};
int mid = (left+right)/2;
Build(root->l, left, mid);
Build(root->r, mid+1, right);
root->update();
}
int wolf_left(node* root, int left, int right, int qL, int qR, int val){
if(left > qR || right < qL) return -1;
if(left >= qL && right <= qR){
if(root->maxi <= val) return left;
}
int mid = (left+right)/2;
if(mid < qL) return wolf_left(root->r, mid+1, right, qL, qR, val);
if(mid+1 > qR) return wolf_left(root->l, left, mid, qL, qR, val);
if(wolf_left(root->r, mid+1, right, qL, qR, val) == mid+1){
return wolf_left(root->l, left, mid, qL, qR, val);
}
return wolf_left(root->r, mid+1, right, qL, qR, val);
}
int wolf_right(node* root, int left, int right, int qL, int qR, int val){
if(left > qR || right < qL) return -1;
if(left >= qL && right <= qR){
if(root->maxi <= val) return right;
}
int mid = (left+right)/2;
if(mid < qL) return wolf_right(root->r, mid+1, right, qL, qR, val);
if(mid+1 > qR) return wolf_right(root->l, left, mid, qL, qR, val);
if(wolf_right(root->l, left, mid, qL, qR, val) == mid){
return wolf_right(root->r, mid+1, right, qL, qR, val);
}
return wolf_right(root->l, left, mid, qL, qR, val);
}
int human_right(node* root, int left, int right, int qL, int qR, int val){
if(left > qR || right < qL) return -1;
//cout << "HUMAN R " << left << ' ' << right << ' ' << qL << ' ' << qR << endl;
if(left >= qL && right <= qR){
if(root->mini >= val) return right;
}
int mid = (left+right)/2;
if(mid < qL) return human_right(root->r, mid+1, right, qL, qR, val);
if(mid+1 > qR) return human_right(root->l, left, mid, qL, qR, val);
if(human_right(root->l, left, mid, qL, qR, val) == mid){
//cout << "OK for " << left << ' ' << right << endl;
return human_right(root->r, mid+1, right, qL, qR, val);
}
return human_right(root->l, left, mid, qL, qR, val);
}
int human_left(node* root, int left, int right, int qL, int qR, int val){
if(left > qR || right < qL) return -1;
if(left >= qL && right <= qR){
if(root->mini >= val) return left;
}
int mid = (left+right)/2;
if(mid < qL) return human_left(root->r, mid+1, right, qL, qR, val);
if(mid+1 > qR) return human_left(root->l, left, mid, qL, qR, val);
if(human_left(root->r, mid+1, right, qL, qR, val) == mid+1){
return human_left(root->l, left, mid, qL, qR, val);
}
return human_left(root->r, mid+1, right, qL, qR, val);
}
pair<int, int> query(node* root, int left, int right, int qL, int qR){
if(left > qR || right < qL) return {INT_MAX, INT_MIN};
if(left >= qL && right <= qR) return {root->mini, root->maxi};
int mid = (left+right)/2;
pair<int, int> L = query(root->l, left, mid, qL, qR);
pair<int, int> R = query(root->r, mid+1, right, qL, qR);
return {min(L.first, R.first), max(L.second, R.second)};
}
///////////////////////////////////////////////////////////////////////
void dfs(vector< vector< int > >& Graph, int last, int nodee){
v.push_back(nodee);
for(int a : Graph[nodee]){
if(a == last) continue;
dfs(Graph, nodee, a);
}
}
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 > > Graph(N);
for(int i = 0; i < M; i++){
Graph[X[i]].push_back(Y[i]);
Graph[Y[i]].push_back(X[i]);
}
vector<int> A(Q);
int beg = -1;
for(int i = 0; i < N; i++){
if(Graph[i].size() == 1){
beg = i;
break;
}
}
v.resize(1);
dfs(Graph, -1, beg);
node* root = new node{NULL,NULL,0,0};
Build(root, 1, N);
vector< int > pos(N);
for(int i = 1; i <= N; i++){
pos[v[i]] = i;
}
/*for(int a : v) cout << a << ' ';
cout << endl;*/
for(int i = 0; i < Q; i++){
if(S[i] < L[i] || E[i] > R[i]){
A[i] = 0;
continue;
}
if(pos[S[i]] < pos[E[i]]){
int indexL = human_right(root, 1, N, pos[S[i]], pos[E[i]], L[i]);
int indexR = wolf_left(root, 1,N, pos[S[i]], pos[E[i]], R[i]);
//cout << "OK " << indexL << ' ' << indexR << endl;
if(query(root, 1, N, indexL+1, indexR-1).first > L[i] && query(root, 1, N, indexL+1, indexR-1).second < R[i]){
A[i] = 1;
}else{
A[i] = false;
}
}else{
int indexR = human_left(root, 1, N, pos[S[i]], pos[E[i]], L[i]);
int indexL = wolf_right(root, 1,N, pos[S[i]], pos[E[i]], R[i]);
if(query(root, 1, N, indexL+1, indexR-1).first > L[i] && query(root, 1, N, indexL+1, indexR-1).second < R[i]){
A[i] = 1;
}else{
A[i] = false;
}
}
}
return A;
}
