#include "werewolf.h"
#include <iostream>
#include <algorithm>
#include <vector>
using namespace std;
#define pb push_back
const int MAX_N = 4e5 + 5;
const int MAX_LOG = 20;
vector <int> g[MAX_N];
vector <int> T1[MAX_N];
vector <int> T2[MAX_N];
int dad1[MAX_N][MAX_LOG], dad2[MAX_N][MAX_LOG];
int set1[MAX_N], set2[MAX_N];
int S(int x, int SET[])
{
if (x != SET[x])
return x = S(SET[x], SET);
else
return x;
}
void unire(int x, int y, int SET[], int dad[MAX_N][MAX_LOG])
{
int xx = S(x, SET);
int yy = S(y, SET);
if (xx == yy)
return;
dad[yy][0] = x;
SET[yy] = x;
}
void arb(int dad[MAX_N][MAX_LOG], int n, vector <int> T[])
{
for (int i = 1; i <= n; i++)
{
T[i].pb(dad[i][0]);
T[dad[i][0]].pb(i);
}
}
int timp;
int in1[MAX_N], out1[MAX_N], in2[MAX_N], out2[MAX_N];
int intime[MAX_N], outtime[MAX_N];
void dfs1(int nod, int dad = 0)
{
in1[nod] = ++timp;
for (auto x : T1[nod])
{
if (x == dad || !x)
continue;
dfs1(x, nod);
}
out1[nod] = timp;
}
int aib[MAX_N * 2];
int N;
int lsb(int x)
{
return x & (-x);
}
int query(int pz)
{
int s = 0;
while (pz > 0)
{
s += aib[pz];
pz -= lsb(pz);
}
return s;
}
void update(int pz, int val)
{
while (pz <= N)
{
aib[pz] += val;
pz += lsb(pz);
}
}
void dfs2(int nod, int dad = 0)
{
in2[nod] = ++timp;
intime[timp] = nod;
for (auto x : T2[nod])
{
if (x == dad || !x)
continue;
dfs2(x, nod);
}
out2[nod] = timp;
}
struct Interval{
int x, l, r, tip, ind;
};
bool cmp(Interval a, Interval b)
{
return a.x < b.x;
}
Interval interv[MAX_N];
vector <int> A;
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 i; N = n;
for (i = 0; i < X.size(); i++)
{
g[X[i] + 1].pb(Y[i] + 1);
g[Y[i] + 1].pb(X[i] + 1);
}
for (i = 1; i <= n; i++)
set1[i] = set2[i] = i;
///pt l <=
for (i = 1; i <= n; i++)
for (auto x : g[i])
if (x < i)
unire(i, x, set1, dad1);
arb(dad1, n, T1);
timp = 0;
dfs1(n);
///pt <= r
for (i = n; i; i--)
for (auto x : g[i])
if (i < x)
unire(i, x, set2, dad2);
arb(dad2, n, T2);
timp = 0;
dfs2(1);
///LIFT
for (int j = 1; j < MAX_LOG; j++)
for (i = 1; i <= n; i++)
{
dad1[i][j] = dad1[dad1[i][j - 1]][j - 1];
dad2[i][j] = dad2[dad2[i][j - 1]][j - 1];
}
int cnt = 0;
for (i = 0; i < S.size(); i++)
{
int s = S[i], e = E[i], l = L[i], r = R[i];
s++, e++, l++, r++;
int lg = MAX_LOG - 1;
while (0 <= lg)
{
if (l <= dad2[s][lg])
s = dad2[s][lg];
lg--;
}
lg = MAX_LOG - 1;
while (0 <= lg)
{
if (dad1[e][lg] && dad1[e][lg] <= r)
e = dad1[e][lg];
lg--;
}
interv[++cnt] = {in2[s] - 1, in1[e], out1[e], -1, i};
interv[++cnt] = {out2[s], in1[e], out1[e], 1, i};
}
sort(interv + 1, interv + cnt + 1, cmp);
A.resize(S.size());
int j = 1;
for (i = 1; i <= cnt; i++)
{
while (j <= interv[i].x)
{
update(in1[intime[j]], 1);
j++;
}
A[interv[i].ind] += interv[i].tip * (query(interv[i].r) - query(interv[i].l - 1));
}
for (i = 0; i < A.size(); i++)
if (A[i] > 0)
A[i] = 1;
else
A[i] = 0;
return A;
}/*
vector <int> x;
vector <int> y;
vector <int> s;
vector <int> e;
vector <int> l;
vector <int> r;
int main()
{
int n, m, q, i;
cin >> n >> m >> q;
x.resize(m);
y.resize(m);
for (i = 0; i < m; i++)
cin >> x[i];
for (i = 0; i < m; i++)
cin >> y[i];
s.resize(q);
e.resize(q);
l.resize(q);
r.resize(q);
for (i = 0; i < q; i++)
cin >> s[i];
for (i = 0; i < q; i++)
cin >> e[i];
for (i = 0; i < q; i++)
cin >> l[i];
for (i = 0; i < q; i++)
cin >> r[i];
vector <int> aaa = check_validity(n, x, y, s, e, l, r);
aaa.resize(q);
for(i = 0; i < q; i++)
cout << aaa[i];
return 0;
}*/
