#include "werewolf.h"
#include <bits/stdc++.h>
using namespace std;
#define all(x) x.begin(), x.end()
struct FakeFenwick
{
vector<vector<int>> fw, val;
int n;
FakeFenwick() {}
FakeFenwick(int n) : n(n), val(n + 1, vector<int>()), fw(n + 1) {}
bool iscc = 0;
void fakeU(int x, int y)
{
iscc = 0;
for (; x <= n; x += x & -x)
val[x].push_back(y);
}
void cc()
{
if (iscc)
return;
for (int x = 1; x <= n; x++)
{
sort(all(val[x]));
val[x].erase(unique(all(val[x])), val[x].end());
fw[x].resize(val[x].size() + 1);
}
iscc = 1;
}
void update(int x, int y, int v)
{
assert(iscc);
for (; x <= n; x += x & -x)
{
int yy = upper_bound(all(val[x]), y) - val[x].begin();
for (; yy <= val[x].size(); yy += yy & -yy)
{
fw[x][yy] += v;
}
}
}
int get(int x, int y)
{
assert(iscc);
int res = 0;
for (; x; x -= x & -x)
{
int yy = upper_bound(all(val[x]), y) - val[x].begin();
for (; yy; yy -= yy & -yy)
{
res += fw[x][yy];
}
}
return res;
}
int get(int x1, int y1, int x2, int y2)
{
return get(x2, y2) - get(x2, y1 - 1) - get(x1 - 1, y2) + get(x1 - 1, y1 - 1);
}
};
struct dsu
{
int N, t;
vector<vector<int>> adj, st;
vector<int> par, pos, in, out;
dsu() {}
dsu(int N)
{
this->N = N;
par.resize(N);
iota(all(par), 0);
adj.resize(N);
pos.resize(N);
in.resize(N);
out.resize(N);
}
int find(int u)
{
return u == par[u] ? u : par[u] = find(par[u]);
}
void join(vector<int> v)
{
set<int> s;
for (int i : v)
s.insert(find(i));
par.push_back(N);
adj.push_back({});
pos.push_back(-1);
in.push_back(-1);
out.push_back(-1);
for (int i : s)
par[i] = N, adj[N].push_back(i);
N++;
}
void dfs(int u)
{
//cout << u << ' ';
in[u] = t++;
for (int v : adj[u])
{
st[v][0] = u;
dfs(v);
}
out[u] = t;
//cout << u << ' ';
}
void dfs()
{
st = vector<vector<int>>(N, vector<int>(20));
t = 1;
dfs(N - 1);
st[N - 1][0] = N - 1;
for (int i = 1; i < 20; i++)
{
for (int j = 0; j < N; j++) st[j][i] = st[st[j][i - 1]][i - 1];
}
}
int get(int u, int k)
{
for (int i = 19; i >= 0; i--)
{
if (st[u][i] <= k) u = st[u][i];
}
return u;
}
};
vector<int> check_validity(int N, vector<int> X, vector<int> Y, vector<int> S, vector<int> E, vector<int> L, vector<int> R)
{
vector<vector<int>> adj(N);
int M = X.size();
for (int i = 0; i < M; i++)
{
adj[X[i]].push_back(Y[i]);
adj[Y[i]].push_back(X[i]);
}
int Q = S.size();
vector<int> res(Q);
dsu dsuL(N), dsuR(N);
for (int i = N - 1; i >= 0; i--)
{
vector<int> v = {i};
for (int j : adj[i])
if (j > i)
v.push_back(j);
dsuL.join(v);
}
for (int i = 0; i < N; i++)
{
vector<int> v = {i};
for (int j : adj[i])
if (j < i)
v.push_back(j);
dsuR.join(v);
}
//out << "LEFT ";
dsuL.dfs();
//cout << "\nRIGHT ";
dsuR.dfs();
//cout << '\n';
FakeFenwick tree(N + M + 5);
for (int i = 0; i < N; i++)
{
int x = dsuL.in[i], y = dsuR.in[i];
//cout << x << ' ' << y << '\n';
tree.fakeU(x, y);
}
tree.cc();
for (int i = 0; i < N; i++)
{
int x = dsuL.in[i], y = dsuR.in[i];
tree.update(x, y, 1);
}
for (int i = 0; i < Q; i++)
{
int f = dsuL.get(S[i], 2 * N - 1 - L[i]), s = dsuR.get(E[i], N + R[i]);
int lx = dsuL.in[f], rx = dsuL.out[f] - 1;
int ly = dsuR.in[s], ry = dsuR.out[s] - 1;
//cout << lx << ' ' << rx << ' ' << ly << ' ' << ry << ' ' << tree.get(lx, ly, rx, ry) << '\n';
res[i] = (tree.get(lx, ly, rx, ry) > 0);
}
return res;
}
