#include "werewolf.h"
#include <bits/stdc++.h>
using namespace std;
#define m_p make_pair
#define fi first
#define se second
#define all(x) (x).begin(),(x).end()
#define sz(x) ((int)(x).size())
typedef long long ll;
const int N = 400005;
int n, m, qq;
vector<int> g[N];
void dfs00(int x, int ul, int ur, vector<bool>& c)
{
if (!(ul <= x && x <= ur))
return;
if (c[x])
return;
c[x] = true;
for (int i = 0; i < g[x].size(); ++i)
{
int h = g[x][i];
dfs00(h, ul, ur, c);
}
}
vector<int> solv0(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)
{
vector<int> ans;
for (int i = 0; i < qq; ++i)
{
vector<bool> cs, ce;
cs.assign(n, false);
ce.assign(n, false);
dfs00(S[i], L[i], n - 1, cs);
dfs00(E[i], 0, R[i], ce);
for (int x = 0; x < n; ++x)
{
if (cs[x] && ce[x])
{
ans.push_back(1);
break;
}
}
if (sz(ans) != (i + 1))
ans.push_back(0);
}
return ans;
}
int p0[N];
int fi(int x)
{
if (x == p0[x])
return x;
return p0[x] = fi(p0[x]);
}
vector<vector<int> > g1, g2;
int tin1[N], tout1[N], ti1;
int tin2[N], tout2[N], ti2;
const int k = 20;
int p1[N][k], p2[N][k];
void dfs0(int x, int p0, vector<vector<int> >& g, int tin[], int tout[], int& ti, int p[][k])
{
tin[x] = ++ti;
p[x][0] = p0;
for (int i = 1; i < k; ++i)
p[x][i] = p[p[x][i - 1]][i - 1];
for (int i = 0; i < g[x].size(); ++i)
{
int h = g[x][i];
dfs0(h, x, g, tin, tout, ti, p);
}
tout[x] = ti;
}
int go1(int x, int l)
{
for (int i = k - 1; i >= 0; --i)
{
if (p1[x][i] >= l)
x = p1[x][i];
}
return x;
}
int go2(int x, int r)
{
for (int i = k - 1; i >= 0; --i)
{
if (p2[x][i] <= r)
x = p2[x][i];
}
return x;
}
int rtin2[N], rtin1[N];
int z;
int t[N * k];
int ul[N * k], ur[N * k];
int ubd(int tl, int tr, int x, int pos)
{
int ypos = ++z;
ul[ypos] = ul[pos];
ur[ypos] = ur[pos];
t[ypos] = t[pos];
if (tl == tr)
{
t[ypos]++;
return ypos;
}
int m = (tl + tr) / 2;
if (x <= m)
ul[ypos] = ubd(tl, m, x, ul[pos]);
else
ur[ypos] = ubd(m + 1, tr, x, ur[pos]);
t[ypos] = t[ul[ypos]] + t[ur[ypos]];
return ypos;
}
int qry(int tl, int tr, int l, int r, int pos)
{
if (l > r)
return 0;
if (tl == l && tr == r)
return t[pos];
int m = (tl + tr) / 2;
return (qry(tl, m, l, min(m, r), ul[pos]) +
qry(m + 1, tr, max(m + 1, l), r, ur[pos]));
}
int root[N];
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)
{
n = N_;
m = sz(X);
qq = sz(S);
for (int i = 0; i < m; ++i)
{
int x = X[i];
int y = Y[i];
g[x].push_back(y);
g[y].push_back(x);
}
vector<int> ans;
g1.resize(n);
g2.resize(n);
for (int x = 0; x < n; ++x)
p0[x] = x;
vector<pair<int, int> > v;
for (int i = 0; i < m; ++i)
{
if (X[i] > Y[i])
swap(X[i], Y[i]);
v.push_back(m_p(X[i], Y[i]));
}
sort(all(v));
reverse(all(v));
for (int i = 0; i < m; ++i)
{
int x = v[i].fi;
int y = v[i].se;
x = fi(x);
y = fi(y);
if (x == y)
continue;
g1[x].push_back(y);
p0[y] = x;
}
for (int x = 0; x < n; ++x)
p0[x] = x;
v.clear();
for (int i = 0; i < m; ++i)
{
swap(X[i], Y[i]);
v.push_back(m_p(X[i], Y[i]));
}
sort(all(v));
for (int i = 0; i < m; ++i)
{
int x = v[i].fi;
int y = v[i].se;
x = fi(x);
y = fi(y);
if (x == y)
continue;
g2[x].push_back(y);
p0[y] = x;
}
dfs0(0, 0, g1, tin1, tout1, ti1, p1);
dfs0(n - 1, n - 1, g2, tin2, tout2, ti2, p2);
for (int x = 0; x < n; ++x)
{
rtin2[tin2[x]] = x;
rtin1[tin1[x]] = x;
}
for (int i = 1; i <= n; ++i)
root[i] = ubd(1, n, tin2[rtin1[i]], root[i - 1]);
for (int ii = 0; ii < qq; ++ii)
{
int x = S[ii];
int y = E[ii];
int l = L[ii];
int r = R[ii];
x = go1(x, l);
y = go2(y, r);
int s = qry(1, n, tin2[y], tout2[y], root[tout1[x]])
- qry(1, n, tin2[y], tout2[y], root[tin1[x] - 1]);
if (s)
ans.push_back(1);
else
ans.push_back(0);
}
//if (ans != solv0(N_, X, Y, S, E, L, R))
// printf("WA\n");
return ans;
}
