#include "werewolf.h"
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
struct seg{
int lb=0, rb=0;
vector<int> v;
seg *l=nullptr, *r=nullptr;
void ext(){
if(not l and lb!=rb){
int mb = (lb+rb)/2;
l = new seg{lb, mb}, r = new seg{mb+1, rb};
}
}
void build(vector<vector<int>> &vv){
if(lb==rb){
v = vv[lb];
}else{
ext();
l->build(vv);
r->build(vv);
merge(l->v.begin(), l->v.end(), r->v.begin(), r->v.end(), back_inserter(v));
}
}
ll qry(int lox, int hix, int loy, int hiy){
if(hix<lb or rb < lox){
return 0;
}
if(lox <= lb and rb <= hix){
int ll = lower_bound(v.begin(), v.end(), loy) - v.begin();
int rr = lower_bound(v.begin(), v.end(), hiy + 1) - v.begin() - 1;
return max(0, rr - ll + 1);
}
ext();
return l->qry(lox, hix, loy, hiy) + r->qry(lox, hix, loy, hiy);
}
};
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) {
int Q = S.size();
int M = X.size();
std::vector<int> A(Q);
auto calc = [&](vector<array<int, 3>> e){
int t = N;
vector<vector<int>> g(2*N+5);
vector<int> p(2*N+5, -1);
auto find = [&](auto find, int u){
if(p[u]==-1) return u;
return p[u]=find(find, p[u]);
};
auto join = [&](int u, int v){
int a = find(find, u), b = find(find, v);
if(a!=b){
g[t].push_back(a);
g[t].push_back(b);
p[a]=t;
p[b]=t;
t++;
}
};
for(auto [cost, u, v]:e){
join(u, v);
}
vector<int> order(N);
int num = 0;
auto dfs = [&](auto dfs, int u) -> void {
for(int v:g[u]){
dfs(dfs, v);
}
if(u<N)
order[u]=num++;
};
dfs(dfs, t-1);
return order;
};
vector<array<int, 2>> ivx(Q), ivy(Q);
auto calcinterval = [&](vector<array<int, 3>> e, vector<int> order){
int t = N;
vector<int> p(N);
vector<array<int, 2>> mask(N);
for(int i=0; i<N; i++) {
mask[i][0]=mask[i][1]=order[i];
p[i]=i;
}
auto find = [&](auto find, int u){
if(p[u]==u) return u;
return p[u]=find(find, p[u]);
};
auto join = [&](int u, int v){
int a = find(find, u), b = find(find, v);
if(a!=b){
p[a] = b;
mask[b][0] = min(mask[b][0], mask[a][0]);
mask[b][1] = max(mask[b][1], mask[a][1]);
}
};
vector<array<int, 2>> todo;
for(int i=0; i<Q; i++){
todo.push_back({L[i], i});
}
sort(todo.begin(), todo.end());
for(auto [cost, u, v]:e){
while(todo.size() and todo.back()[0] > cost){
auto [l, id]=todo.back();
todo.pop_back();
ivx[id] = mask[find(find, S[id])];
}
join(u, v);
}
while(todo.size()){
auto [l, id]=todo.back();
todo.pop_back();
ivx[id] = mask[find(find, S[id])];
}
};
auto calcinterval2 = [&](vector<array<int, 3>> e, vector<int> order){
int t = N;
vector<int> p(N, -1);
vector<array<int, 2>> mask(N);
for(int i=0; i<N; i++) {
mask[i][0]=mask[i][1]=order[i];
p[i]=i;
}
auto find = [&](auto find, int u){
if(p[u]==u) return u;
return p[u]=find(find, p[u]);
};
auto join = [&](int u, int v){
int a = find(find, u), b = find(find, v);
if(a!=b){
p[a] = b;
mask[b][0] = min(mask[b][0], mask[a][0]);
mask[b][1] = max(mask[b][1], mask[a][1]);
}
};
vector<array<int, 2>> todo;
for(int i=0; i<Q; i++){
todo.push_back({R[i], i});
}
sort(todo.begin(), todo.end());
reverse(todo.begin(), todo.end());
for(auto [cost, u, v]:e){
while(todo.size() and todo.back()[0] < cost){
auto [r, id]=todo.back();
todo.pop_back();
ivy[id] = mask[find(find, E[id])];
}
join(u, v);
}
while(todo.size()){
auto [r, id]=todo.back();
todo.pop_back();
ivy[id] = mask[find(find, E[id])];
}
};
vector<array<int, 3>> ex, ey;
for(int i=0; i<M; i++){
ex.push_back({min(X[i], Y[i]), X[i], Y[i]});
ey.push_back({max(X[i], Y[i]), X[i], Y[i]});
}
sort(ex.begin(), ex.end());
reverse(ex.begin(), ex.end());
sort(ey.begin(), ey.end());
auto x = calc(ex);
auto y = calc(ey);
calcinterval(ex, x);
calcinterval2(ey, y);
seg tree = {0, N-1};
vector<vector<int>> vv(N);
for(int i=0; i<N; i++){
vv[x[i]].push_back(y[i]);
}
tree.build(vv);
for(int i=0; i<Q; i++){
auto [x1, x2] = ivx[i];
auto [y1, y2] = ivy[i];
A[i] = tree.qry(x1, x2, y1, y2) > 0;
}
/*
cout<<endl;
for(int i=0; i<N; i++) cout << i << " " << x[i] << endl;
cout<<endl;
for(int i=0; i<N; i++) cout << i << " " << y[i] << endl;
cout<<endl;
for(int i=0; i<Q; i++) cout << ivx[i][0] << " " << ivx[i][1] << endl;
cout<<endl;
for(int i=0; i<Q; i++) cout << ivy[i][0] << " " << ivy[i][1] << endl;
*/
return A;
}
