#include "werewolf.h"
#include<bits/stdc++.h>
using namespace std;
int cm, cnt;
vector<int> vs, ve, sl, sr, el, er, pp, pm, pl, pr;
vector<vector<int>> g;
int n;
vector<int> w;
vector<vector<int>> st;
void build(int node=1, int tl=0, int tr=n-1){
if (tl == tr){
st[node].push_back(w[tl]);
return;
}
int tm = (tl+tr)/2;
build(node*2, tl, tm);
build(node*2+1, tm+1, tr);
for (int x : st[node*2]) st[node].push_back(x);
for (int x : st[node*2+1]) st[node].push_back(x);
sort(st[node].begin(), st[node].end());
}
bool isthere(int node, int le, int re){
for (int x : st[node]){
if (le <= x && x <= re) return true;
}
return false;
/*int l = 0, r = st[node].size();
while (l != r-1){
int m = (l+r)/2;
if (st[node][m] >= le) r = m;
else l = m;
}
if (r == st[node].size() || st[node][r] > re) return false;
return true;*/
}
bool query(int ls, int rs, int le, int re, int node=1, int tl=0, int tr=n-1){
if (ls <= tl && tr <= rs) return isthere(node, le, re);
int tm = (tl+tr)/2;
if (ls <= tm && query(ls, rs, le, re, node*2, tl, tm)) return true;
if (tm+1 <= rs && query(ls, rs, le, re, node*2+1, tm+1, tr)) return true;
return false;
}
int find(int a){
if (a == pp[a]) return pp[a];
return pp[a] = find(pp[a]);
}
void merge(int a, int b, bool sht=false){
a = find(a);
b = find(b);
if (a == b) return;
pp[b] = a;
pl[a] = min(pl[a], pl[b]);
pr[a] = max(pr[a], pr[b]);
if (sht) return;
if (pm[a] == -1) g[cm].push_back(-a-1);
else g[cm].push_back(pm[a]);
if (pm[b] == -1) g[cm].push_back(-b-1);
else g[cm].push_back(pm[b]);
pm[a] = cm;
cm++;
}
void dfs(int cur, vector<int>& v){
if (cur < 0){
v[-cur-1] = cnt;
cnt++;
return;
}
for (int next : g[cur]) dfs(next, v);
}
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;
int M = X.size();
int Q = S.size();
vector<pair<int,pair<int,int>>> es, ee;
for (int i=0; i<M; i++){
es.push_back({min(X[i], Y[i]), {X[i], Y[i]}});
ee.push_back({max(X[i], Y[i]), {X[i], Y[i]}});
}
vector<pair<int,pair<int,int>>> qs, qe;
for (int i=0; i<Q; i++){
qs.push_back({L[i], {S[i], i}});
qe.push_back({R[i], {E[i], i}});
}
sort(es.begin(), es.end());
sort(ee.begin(), ee.end());
sort(qs.begin(), qs.end());
sort(qe.begin(), qe.end());
vs.resize(N);
ve.resize(N);
sl.resize(Q);
sr.resize(Q);
el.resize(Q);
er.resize(Q);
pp.resize(N);
pm.resize(N);
pl.resize(N);
pr.resize(N);
for (int i=0; i<N; i++){
pp[i] = i;
pm[i] = -1;
}
g.assign(N-1, vector<int>(0));
cm = 0;
for (int i=M-1; i>=0; i--) merge(es[i].second.first, es[i].second.second);
cnt = 0;
dfs(N-2, vs);
for (int i=0; i<N; i++){
pp[i] = i;
pl[i] = vs[i];
pr[i] = vs[i];
}
int cur = Q-1;
for (int i=M-1; i>=0; i--){
while (cur >= 0 && es[i].first < qs[cur].first){
sl[qs[cur].second.second] = pl[find(qs[cur].second.first)];
sr[qs[cur].second.second] = pr[find(qs[cur].second.first)];
cur--;
}
merge(es[i].second.first, es[i].second.second, true);
}
while (cur >= 0){
sl[qs[cur].second.second] = pl[find(qs[cur].second.first)];
sr[qs[cur].second.second] = pr[find(qs[cur].second.first)];
cur--;
}
for (int i=0; i<N; i++){
pp[i] = i;
pm[i] = -1;
}
g.assign(N-1, vector<int>(0));
cm = 0;
for (int i=0; i<M; i++) merge(ee[i].second.first, ee[i].second.second);
cnt = 0;
dfs(N-2, ve);
for (int i=0; i<N; i++){
pp[i] = i;
pl[i] = ve[i];
pr[i] = ve[i];
}
cur = 0;
for (int i=0; i<M; i++){
while (cur < Q && ee[i].first > qe[cur].first){
el[qe[cur].second.second] = pl[find(qe[cur].second.first)];
er[qe[cur].second.second] = pr[find(qe[cur].second.first)];
cur++;
}
merge(ee[i].second.first, ee[i].second.second, true);
}
while (cur < Q){
el[qe[cur].second.second] = pl[find(qe[cur].second.first)];
er[qe[cur].second.second] = pr[find(qe[cur].second.first)];
cur++;
}
w.resize(N);
st.resize(4*N);
for (int i=0; i<N; i++) w[vs[i]] = ve[i];
build();
vector<int> A(Q);
for (int i=0; i<Q; i++) A[i] = query(sl[i], sr[i], el[i], er[i]);
return A;
}
