#include "werewolf.h"
#include <algorithm>
#include <iostream>
#include <numeric>
#include <vector>
typedef long long llong;
const int MAXLOG = 20 + 5;
const int MAXN = 200000 + 10;
const int INF = 1e9;
int n, m, q;
struct DSU
{
int par[MAXN];
int dep[MAXN];
int min[MAXN];
int max[MAXN];
void reset()
{
std::fill(dep + 1, dep + 1 + n, 1);
std::iota(par + 1, par + 1 + n, 1);
std::iota(min + 1, min + 1 + n, 1);
std::iota(max + 1, max + 1 + n, 1);
}
int find(int node)
{
if (par[node] == node) return node;
return par[node] = find(par[node]);
}
inline void connect(int u, int v)
{
u = find(u); v = find(v);
if (u == v)
{
return;
}
if (dep[u] > dep[v])
{
std::swap(u, v);
}
if (dep[u] == dep[v])
{
dep[v]++;
}
min[v] = std::min(min[u], min[v]);
max[v] = std::max(max[u], max[v]);
par[u] = v;
}
inline bool areConnected(int u, int v)
{
return find(u) == find(v);
}
};
struct Sparse
{
int sparse[MAXLOG][MAXN];
void build(int s[])
{
for (int i = 1 ; i <= n ; ++i)
{
sparse[0][i] = s[i];
}
for (int log = 1 ; (1 << log) <= n ; ++log)
{
for (int i = 1 ; i <= n ; ++i)
{
sparse[log][i] = sparse[log - 1][sparse[log - 1][i]];
}
}
}
inline int findLastBigger(int node, int value)
{
for (int log = MAXLOG - 1 ; log >= 0 ; --log)
{
if (sparse[log][node] >= value)
{
node = sparse[log][node];
}
}
return node;
}
inline int findLastLower(int node, int value)
{
for (int log = MAXLOG - 1 ; log >= 0 ; --log)
{
if (sparse[log][node] <= value && sparse[log][node] != 0)
{
node = sparse[log][node];
}
}
return node;
}
};
struct BIT
{
int tree[MAXN];
inline void update(int pos, int value)
{
pos++;
for (int idx = pos ; idx <= n ; idx += idx & (-idx))
{
tree[idx] += value;
}
}
inline int query(int pos)
{
pos++;
int res = 0;
for (int idx = pos ; idx > 0 ; idx -= idx & (-idx))
{
res += tree[idx];
}
return res;
}
};
int inMIN[MAXN];
int inMAX[MAXN];
int outMIN[MAXN];
int outMAX[MAXN];
int parMIN[MAXN];
int parMAX[MAXN];
int inMAXtour[MAXN];
std::vector <int> tourMIN;
std::vector <int> tourMAX;
std::vector <int> g[MAXN];
std::vector <int> treeMIN[MAXN];
std::vector <int> treeMAX[MAXN];
Sparse sparseMAX;
Sparse sparseMIN;
BIT fenwick;
DSU dsu;
void makeMAXTour(int node)
{
inMAXtour[node] = inMAX[node] = tourMAX.size();
tourMAX.push_back(node);
for (const int &i : treeMAX[node])
{
makeMAXTour(i);
parMAX[i] = node;
}
outMAX[node] = tourMAX.size() - 1;
}
void makeMINTour(int node)
{
inMIN[node] = tourMIN.size();
tourMIN.push_back(inMAXtour[node]);
for (const int &i : treeMIN[node])
{
makeMINTour(i);
parMIN[i] = node;
}
outMIN[node] = tourMIN.size() - 1;
}
struct Query
{
int idx, l, r;
bool add;
};
std::vector <int> ans;
std::vector <Query> queries[MAXN];
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 = X.size();
q = S.size();
for (int i = 0 ; i < m ; ++i)
{
g[X[i] + 1].push_back(Y[i] + 1);
g[Y[i] + 1].push_back(X[i] + 1);
}
dsu.reset();
for (int i = n ; i >= 1 ; --i)
{
for (const int &j : g[i])
{
if (j < i || dsu.areConnected(i, j))
{
continue;
}
treeMAX[i].push_back(dsu.min[dsu.find(j)]);
dsu.connect(i, j);
}
}
dsu.reset();
for (int i = 1 ; i <= n ; ++i)
{
for (const int &j : g[i])
{
if (j > i || dsu.areConnected(i, j))
{
continue;
}
treeMIN[i].push_back(dsu.max[dsu.find(j)]);
dsu.connect(i, j);
}
}
makeMAXTour(1);
makeMINTour(n);
sparseMAX.build(parMAX);
sparseMIN.build(parMIN);
for (int i = 0 ; i < q ; ++i)
{
int minRoot = sparseMIN.findLastLower(E[i] + 1, R[i] + 1);
int maxRoot = sparseMAX.findLastBigger(S[i] + 1, L[i] + 1);
if (inMIN[minRoot] > 0) queries[inMIN[minRoot] - 1].push_back({i, inMAX[maxRoot], outMAX[maxRoot], false});
queries[outMIN[minRoot]].push_back({i, inMAX[maxRoot], outMAX[maxRoot], true});
}
ans.resize(q);
for (int i = 0 ; i < n ; ++i)
{
fenwick.update(tourMIN[i], 1);
for (const Query &curr : queries[i])
{
if (curr.add) ans[curr.idx] += fenwick.query(curr.r) - fenwick.query(curr.l - 1);
else ans[curr.idx] -= fenwick.query(curr.r) - fenwick.query(curr.l - 1);
}
}
for (int i = 0 ; i < q ; ++i)
{
ans[i] = (ans[i] > 0);
}
return ans;
}
