#include "werewolf.h"
#include <vector>
#include <algorithm>
#include <iostream>
using namespace std;
const int maxN = 200000;
vector<int> edge[maxN];
vector<int> col(maxN);
vector<int> col_list[maxN];
vector<int> minV(maxN); //min value in color i.
vector<int> child1[maxN];
vector<int> order1;
vector<int> pos1(maxN);
vector<int> subtree1(maxN, 1);
int anc1[maxN][20];
vector<int> depth1(maxN);
void dfs1(int u) {
// cerr << "dfs1 " << u << '\n';
pos1[u] = int(order1.size());
order1.push_back(u);
for(int v: child1[u]) {
anc1[v][0] = u;
for(int e = 1; e < 20; e++)
anc1[v][e] = anc1[ anc1[v][e-1] ][e-1];
depth1[v] = depth1[u] + 1;
dfs1(v);
subtree1[u] += subtree1[v];
}
}
vector<int> maxV(maxN);
vector<int> child2[maxN];
vector<int> order2;
vector<int> pos2(maxN);
vector<int> subtree2(maxN, 1);
int anc2[maxN][20];
vector<int> depth2(maxN);
void dfs2(int u) {
pos2[u] = int(order2.size());
order2.push_back(u);
for(int v: child2[u]) {
anc2[v][0] = u;
for(int e = 1; e < 20; e++)
anc2[v][e] = anc2[ anc2[v][e-1] ][e-1];
depth2[v] = depth2[u] + 1;
dfs2(v);
subtree2[u] += subtree2[v];
}
}
vector<int> init(maxN);
struct segtree {
int l;
int r;
vector<int> V;
segtree* left = NULL;
segtree* right = NULL;
segtree() {
;
}
segtree(int L, int R) {
l = L;
r = R;
if(l == r) {
V.push_back(init[l]);
}
else {
int m = (l+r)/2;
left = new segtree(l, m);
right = new segtree(m+1, r);
for(int v: left->V) V.push_back(v);
for(int v: right->V) V.push_back(v);
sort(V.begin(), V.end());
}
}
bool query(int L, int R, int X, int Y) {
if(R < l || r < L) return 0;
else if(L <= l && r <= R) {
int s = -1;
for(int e = 19; e >= 0; e--) {
if(s + (1 << e) >= V.size()) continue;
if(V[s + (1 << e)] <= Y)
s += (1 << e);
}
if(s == -1) return 0;
return (V[s] >= X);
}
else return left->query(L, R, X, Y) || right->query(L, R, X, Y);
}
};
segtree T;
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 M = X.size();
for(int j = 0; j < M; j++) {
edge[X[j]].push_back(Y[j]);
edge[Y[j]].push_back(X[j]);
}
for(int e = 0; e < 20; e++) {
anc1[0][e] = 0;
anc2[N-1][e] = N-1;
}
depth1[0] = 0;
depth2[N-1] = 0;
for(int i = 0; i < N; i++) {
col_list[i].push_back(i);
col[i] = minV[i] = i;
}
for(int u = N-1; u >= 0; u--) {
for(int v: edge[u]) {
if(v < u) continue;
if(col[v] == col[u]) continue;
child1[u].push_back(minV[col[v]]);
int U = u, V = v;
if(col_list[col[U]].size() < col_list[col[V]].size())
swap(U, V);
int colV = col[V];
for(int x: col_list[colV]) {
col[x] = col[U];
col_list[col[U]].push_back(x);
}
minV[col[U]] = u;
}
}
dfs1(0);
for(int i = 0; i < N; i++) {
col_list[i].clear();
col_list[i].push_back(i);
col[i] = maxV[i] = i;
}
for(int u = 0; u < N; u++) {
for(int v: edge[u]) {
if(v > u) continue;
if(col[v] == col[u]) continue;
child2[u].push_back(maxV[col[v]]);
int U = u, V = v;
if(col_list[col[U]].size() < col_list[col[V]].size())
swap(U, V);
int colV = col[V];
for(int x: col_list[colV]) {
col[x] = col[U];
col_list[col[U]].push_back(x);
}
maxV[col[U]] = u;
}
}
dfs2(N-1);
for(int i = 0; i < N; i++)
init[ pos1[i] ] = pos2[i];
T = segtree(0, N-1);
int Q = S.size();
vector<int> res(Q);
for(int i = 0; i < Q; i++) {
int s = S[i], e = E[i], l = L[i], r = R[i];
for(int x = 19; x >= 0; x--){
if(anc1[s][x] >= l)
s = anc1[s][x];
}
for(int x = 19; x >= 0; x--) {
if(anc2[e][x] <= r)
e = anc2[e][x];
}
res[i] = T.query(pos1[s], pos1[s] + subtree1[s] - 1, pos2[e], pos2[e] + subtree2[e] - 1);
}
return res;
}
