#include <bits/stdc++.h>
using namespace std;
struct Aib {
vector <int> aib;
function <int(int)> lsb = [](int x) { return x & (-x); };
function <int(int)> qry = [&](int p) {
int ans = 0;
while (p)
ans += aib[p], p -= lsb(p);
return ans;
};
Aib(int N) : aib(N + 2, 0) { }
void Update(int poz, int val)
{
poz++;
while (poz < (int)aib.size())
aib[poz] += val, poz += lsb(poz);
}
int Query(int st, int dr)
{
st++, dr++;
return qry(dr) - (st > 0 ? qry(st - 1) : 0);
}
};
struct Tree {
vector <int> stramos, liniarizare;
vector <pair <int, int>> poz_in_liniarizare;
vector <vector <int>> adia;
vector <vector <int>> up;
int root;
Tree(int N) : stramos(N), poz_in_liniarizare(N), adia(N), up(N, vector <int> (20, -1)) {
iota(stramos.begin(), stramos.end(), 0);
}
int FindStramos(int nod) {
if (stramos[nod] != nod)
return stramos[nod] = FindStramos(stramos[nod]);
return stramos[nod];
}
void Dfs(int nod) {
// cerr << "Node " << nod << " has sons ";
// for (auto i : adia[nod])
// cerr << i << ' ';
// cerr << '\n';
for (int i = 1; i < 20; i++)
if (up[nod][i - 1] != -1)
up[nod][i] = up[up[nod][i - 1]][i - 1];
poz_in_liniarizare[nod].first = liniarizare.size();
liniarizare.push_back(nod);
for (auto i : adia[nod])
Dfs(i);
poz_in_liniarizare[nod].second = liniarizare.size() - 1;
}
pair <int, int> Span(int nod, function <bool(int)> ok) {
assert(ok(nod));
for (int i = 19; i >= 0; i--)
if (up[nod][i] != -1 && ok(up[nod][i]))
nod = up[nod][i];
return poz_in_liniarizare[nod];
}
};
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>> graph(N);
for (int i = 0; i < (int)X.size(); i++) {
graph[X[i]].push_back(Y[i]);
graph[Y[i]].push_back(X[i]);
}
Tree small_up(N), big_up(N);
for (int i = 0; i < N; i++) {
for (auto vec : graph[i]) {
int x = big_up.FindStramos(vec);
if (vec < i && x != i) {
big_up.stramos[x] = i;
big_up.up[x][0] = i;
big_up.adia[i].push_back(x);
}
}
}
for (int i = N - 1; i >= 0; i--) {
for (auto vec : graph[i]) {
int x = small_up.FindStramos(vec);
if (vec > i && x != i) {
small_up.stramos[x] = i;
small_up.up[x][0] = i;
small_up.adia[i].push_back(x);
}
}
}
// cerr << "For small_up:\n";
small_up.Dfs(0);
// cerr << "\nFor bi_up:\n";
big_up.Dfs(N - 1);
// cerr << "Finished trees\n";
/// I have built the trees, now I have to check for each node the interval it can reach
int Q = S.size();
vector <int> intersection(Q, 0);
vector <pair <int, int>> to_verify(Q);
vector <vector <pair <int, int>>> events(N + 1); // pentru fiecare pozitie daca trebuie sa scad / sa adaug raspunsul pt un query
Aib aib(N);
for (int i = 0; i < Q; i++) {
auto intervS = small_up.Span(S[i], [&](int nod) -> bool { return nod >= L[i]; });
auto intervE = big_up.Span(E[i], [&](int nod) -> bool { return nod <= R[i]; });
// cerr << "Query i can get from S=" << S[i] << " to ";
// for (int j = intervS.first; j <= intervS.second; j++)
// cerr << small_up.liniarizare[j] << ' ';
// cerr << "\nQuery i can get from E=" << E[i] << " to ";
// for (int j = intervE.first; j <= intervE.second; j++)
// cerr << big_up.liniarizare[j] << ' ';
// cerr << "\n\n";
to_verify[i] = intervE;
events[intervS.first].push_back({ i, -1 });
events[intervS.second + 1].push_back({ i, 1 });
}
// cerr << "Finished adding segments\n";
for (int i = 0; i <= N; i++) {
/// mai intai verific de e de procesat
for (auto op : events[i]) {
int val = aib.Query(to_verify[op.first].first, to_verify[op.first].second);
intersection[op.first] += val * op.second;
}
if (i < N) {
int elem = small_up.liniarizare[i];
int poz_in_big = big_up.poz_in_liniarizare[elem].first;
aib.Update(poz_in_big, 1);
}
}
for (auto & it : intersection) {
assert(it >= 0);
it = min(it, 1);
}
return intersection;
}
