#include "werewolf.h"
#include <bits/stdc++.h>
using namespace std;
int n, m;
const int MXN = 400005, MXK = 20;
int par[MXN][2];
int nextnode[2];
vector<int> subs[MXN][2];
int value[MXN][2];
int parent(int w, int n) {
if (par[n][w] == n) return n;
return par[n][w] = parent(w, par[n][w]);
}
void connect(int w, int a, int b, int val) {
a = parent(w, a);
b = parent(w, b);
if (a == b) return;
int c = nextnode[w];
nextnode[w]++;
par[a][w] = c;
par[b][w] = c;
subs[c][w].push_back(a);
subs[c][w].push_back(b);
}
int prk[MXN][MXK][2];
pair<int, int> bounds[MXN][2];
int offer[MXN];
int posof[MXN][2];
pair<int, int> dfs(int node, int par, int w) {
int mn = INT_MAX, mx = INT_MIN;
prk[node][0][w] = par;
for (int i=1; i<MXK; i++) {
int t = prk[node][i-1][w];
if (t != -1) {
prk[node][i][w] = prk[t][i-1][w];
}
}
if (w == 0) value[node][w] = INT_MAX;
else value[node][w] = INT_MIN;
for (auto x: subs[node][w]) {
pair<int, int> t = dfs(x, node, w);
if (w == 0) value[node][w] = min(value[node][w], value[x][w]);
else value[node][w] = max(value[node][w], value[x][w]);
mn = min(mn, t.first);
mx = max(mx, t.second);
}
if (mn == INT_MAX) {
value[node][w] = node;
offer[w]++;
posof[node][w] = offer[w]-1;
return bounds[node][w] = {offer[w]-1, offer[w]-1};
}
return bounds[node][w] = {mn, mx};
}
int highest(int n, int w, int minok, int maxok) {
for (int i=MXK-1; i>=0; i--) {
int t = prk[n][i][w];
if (t != -1 && value[t][w] >= minok && value[t][w] <= maxok) {
n = t;
}
}
return n;
}
vector<pair<int, int>> points;
vector<int> contents[MXN * 4];
void build(int ind, int l, int r) {
if (l == r) {
contents[ind].push_back(points[l].second);
return;
}
int m = (l + r) / 2;
build(ind * 2, l, m);
build(ind * 2 + 1, m+1, r);
int lp = 0, rp = 0;
while (lp < contents[ind * 2].size() && rp < contents[ind * 2 + 1].size()) {
if (contents[ind*2][lp] < contents[ind*2+1][rp]) {
contents[ind].push_back(contents[ind*2][lp]);
lp++;
}
else {
contents[ind].push_back(contents[ind*2+1][rp]);
rp++;
}
}
while (lp < contents[ind * 2].size()) {
contents[ind].push_back(contents[ind*2][lp]);
lp++;
}
while (rp < contents[ind * 2 + 1].size()) {
contents[ind].push_back(contents[ind*2+1][rp]);
rp++;
}
}
int query(int ind, int l, int r, int ql, int qr, int ml, int mr) {
if (ql <= l && r <= qr) {
return lower_bound(contents[ind].begin(), contents[ind].end(), ml) != upper_bound(contents[ind].begin(), contents[ind].end(), mr);
}
if (ql > r || qr < l) {
return 0;
}
int m = (l + r) / 2;
return query(ind * 2, l, m, ql, qr, ml, mr) + query(ind * 2 + 1, m+1, r, ql, qr, ml, mr);
}
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;
nextnode[0] = nextnode[1] = n;
for (int i=0; i<MXN; i++) {
par[i][0] = par[i][1] = i;
}
for (int i=0; i<n; i++) {
value[i][0] = value[i][1] = i;
}
int Q = S.size();
vector<int> A;
int M = X.size();
m = M;
vector<pair<int, pair<int, int>>> minproc, maxproc;
for (int i=0; i<M; i++) {
int a = X[i], b = Y[i];
minproc.push_back({min(a, b), {a, b}});
maxproc.push_back({max(a, b), {a, b}});
}
sort(minproc.begin(), minproc.end());
reverse(minproc.begin(), minproc.end());
sort(maxproc.begin(), maxproc.end());
for (auto x: minproc) {
int v = x.first;
int a = x.second.first, b = x.second.second;
connect(0, a, b, v);
}
for (auto x: maxproc) {
int v = x.first;
int a = x.second.first, b = x.second.second;
connect(1, a, b, v);
}
for (int i=0; i<MXN; i++) {
for (int j=0; j<MXK; j++) {
prk[i][j][0] = prk[i][j][1] = -1;
}
}
dfs(2 * n - 2, -1, 0);
dfs(2 * n - 2, -1, 1);
for (int i=0; i<n; i++) {
int x = posof[i][0], y = posof[i][1];
points.push_back({x, y});
}
sort(points.begin(), points.end());
build(1, 0, n-1);
for (int i=0; i<Q; i++) {
int s = S[i], e = E[i], l = L[i], r = R[i];
int side = highest(s, 0, l, n-1);
int other = highest(e, 1, 0, r);
A.push_back(query(1, 0, n-1, bounds[side][0].first, bounds[side][0].second, bounds[other][1].first, bounds[other][1].second) > 0);
}
return A;
}
