#include "werewolf.h"
#include<bits/stdc++.h>
#define X first
#define Y second
using namespace std;
typedef pair<int, int> pii;
const int N = 200005, M = 400005, F = 262144, G = 19, inf = 1e9;
int n, m, q, its[N];
vector<pii> edg;
struct event {
int p, l, r, v, i;
bool operator < (const event &T) const {
return p < T.p;
}
};
vector<event> swp;
struct disjoint_set {
int par[2*N];
void init (int X) {
for(int i=1;i<=X;i++) {
par[i] = i;
}
}
int Find (int X) {
if(par[X] == X) return X;
return par[X] = Find(par[X]);
}
int Union (int X, int Y) {
X = Find(X);
Y = Find(Y);
par[Y] = X;
return Y;
}
};
struct connectivity_tree {
int par[G][2*N], inv[N], ord[N], s[2*N], e[2*N], v[2*N], l[2*N], r[2*N], cc, oc;
disjoint_set dsj;
void init (int V) {
dsj.init(2*n);
cc = n;
v[0] = inf;
for(int i=1;i<=n;i++) {
v[i] = V;
}
}
void build () {
for(int i=1;i<G;i++) {
for(int j=1;j<=cc;j++) {
par[i][j] = par[i-1][par[i-1][j]];
}
}
}
void connect (int A, int B, int C) {
if(dsj.Find(A) == dsj.Find(B)) return;
++cc;
int X = dsj.Union(cc, A);
int Y = dsj.Union(cc, B);
par[0][X] = cc;
par[0][Y] = cc;
l[cc] = X;
r[cc] = Y;
v[cc] = C;
}
void trav (int I) {
if(I <= n) {
oc++;
s[I] = oc;
e[I] = oc;
ord[oc] = I;
inv[I] = oc;
}
else {
trav(l[I]);
trav(r[I]);
s[I] = s[l[I]];
e[I] = e[r[I]];
}
}
void trav () {trav(cc);}
pii get (int I, int V) {
for(int i=G;i--;) {
if(v[par[i][I]] <= V) I = par[i][I];
}
return {s[I], e[I]};
}
} a, b;
struct segment_tree {
int v[2*F];
void upd (int P, int V) {
P += F;
while(P) {
v[P] += V;
P /= 2;
}
}
int get (int S, int E) {
S += F;
E += F;
int R = 0;
while(S <= E) {
if(S%2 == 1) R += v[S++];
if(E%2 == 0) R += v[E--];
S /= 2;
E /= 2;
}
return R;
}
} seg;
vector<int> check_validity(int _N, vector<int> _X, vector<int> _Y, vector<int> _S, vector<int> _E, vector<int> _L, vector<int> _R) {
n = _N;
m = (int)_X.size();
q = (int)_L.size();
a.init(-n);
b.init(0);
for(int i=0;i<m;i++) {
int A = _X[i]+1, B = _Y[i]+1;
if(A > B) swap(A, B);
edg.push_back({A, B});
}
sort(edg.begin(), edg.end());
reverse(edg.begin(), edg.end());
for(int i=0;i<m;i++) {
a.connect(edg[i].X, edg[i].Y, -edg[i].X);
}
a.build();
a.trav();
for(int i=0;i<m;i++) {
swap(edg[i].X, edg[i].Y);
}
sort(edg.begin(), edg.end());
for(int i=0;i<m;i++) {
b.connect(edg[i].X, edg[i].Y, edg[i].X);
}
b.build();
b.trav();
for(int i=0;i<q;i++) {
int S, E, X, Y;
tie(S, E) = a.get(_S[i]+1, -_L[i]-1);
tie(X, Y) = b.get(_E[i]+1, _R[i]+1);
swp.push_back({E, X, Y, 1, i});
swp.push_back({S-1, X, Y, -1, i});
}
sort(swp.begin(), swp.end());
int Z = 0;
for(auto &E : swp) {
while(Z < E.p) {
seg.upd(b.inv[a.ord[++Z]], 1);
}
its[E.i] += E.v * seg.get(E.l, E.r);
}
vector<int> ans;
for(int i=0;i<q;i++) {
ans.push_back(its[i] > 0);
}
return ans;
}
