#include "werewolf.h"
#include <iostream>
#include <vector>
#include <set>
#include <algorithm>
const int NMAX = 2e5;
const int LOGMAX = 18;
int _N, M, Q;
std::vector <int> g[NMAX + 2];
int dadSmall[NMAX + 2], dadBig[NMAX + 2];
std::vector <int> dsuSmall[NMAX + 2]; ///in subtree[x] am toate nodurile reach-able <= x
std::vector <int> dsuBig[NMAX + 2]; ///in subree[x] am toate nodurile reach-able >= x
int RootSmall(int x) {
if(x == dadSmall[x])
return x;
return dadSmall[x] = RootSmall(dadSmall[x]);
}
int RootBig(int x) {
if(x == dadBig[x])
return x;
return dadBig[x] = RootBig(dadBig[x]);
}
void JoinSmall(int p, int q) {
int rootP = RootSmall(p);
int rootQ = RootSmall(q);
if(rootP == rootQ)
return ;
if(rootP > rootQ) {
dsuSmall[rootP].push_back(rootQ);
dadSmall[rootQ] = rootP;
} else {
dsuSmall[rootQ].push_back(rootP);
dadSmall[rootP] = rootQ;
}
}
void JoinBig(int p, int q) {
int rootP = RootBig(p);
int rootQ = RootBig(q);
if(rootP == rootQ)
return ;
if(rootP < rootQ) {
dsuBig[rootP].push_back(rootQ);
dadBig[rootQ] = rootP;
} else {
dsuBig[rootQ].push_back(rootP);
dadBig[rootP] = rootQ;
}
}
int liftSmall[LOGMAX + 1][NMAX + 2], liftBig[LOGMAX + 1][NMAX + 2];
std::vector <int> tourSmall;
int lfSmall[NMAX + 2], rgSmall[NMAX + 2];
std::vector <int> tourBig;
int lfBig[NMAX + 2], rgBig[NMAX + 2];
void TraverseSmall(int node) {
//std::cout << node << '\n';
lfSmall[node] = (int)tourSmall.size();
tourSmall.push_back(node);
for(auto it : dsuSmall[node])
TraverseSmall(it);
rgSmall[node] = (int)tourSmall.size() - 1;
}
void TraverseBig(int node) {
//std::cout << node << '\n';
lfBig[node] = (int)tourBig.size();
tourBig.push_back(node);
for(auto it : dsuBig[node])
TraverseBig(it);
rgBig[node] = (int)tourBig.size() - 1;
}
void BuildDSUs() {
for(int i = 0; i < _N; i++) {
dadSmall[i] = i;
dadBig[i] = i;
}
for(int i = 1; i < _N; i++)
for(auto it : g[i])
if(it < i)
JoinSmall(it, i);
for(int i = _N - 2; i >= 0; i--)
for(auto it : g[i])
if(it > i)
JoinBig(it, i);
/*
std::cout << "DSU Small:\n";
for(int i = 0; i < N; i++)
for(auto it : dsuSmall[i])
std::cout << i << ' ' << it << '\n';
std::cout << "DSU Big:\n";
for(int i = 0; i < N; i++)
for(auto it : dsuBig[i])
std::cout << i << ' ' << it << '\n';
*/
TraverseSmall(_N - 1);
TraverseBig(0);
/*
std::cout << "Tour Small\n";
for(auto it : tourSmall)
std::cout << it << ' ';
std::cout << '\n';
for(int i = 0; i < _N; i++)
std::cout << lfSmall[i] << ' ' << rgSmall[i] << '\n';
std::cout << "Tour Big\n";
for(auto it : tourBig)
std::cout << it << ' ';
std::cout << '\n';
for(int i = 0; i < _N; i++)
std::cout << lfBig[i] << ' ' << rgBig[i] << '\n';
*/
}
void PrecomputeLift() {
for(int l = 0; l <= LOGMAX; l++)
for(int i = 0; i < _N; i++)
liftSmall[l][i] = liftBig[l][i] = -1;
//liftSmall[0][N - 1] = -1;
for(int i = 0; i < _N; i++)
for(auto it : dsuSmall[i])
liftSmall[0][it] = i;
for(int l = 1; l <= LOGMAX; l++)
for(int i = 0; i < _N; i++)
if(liftSmall[l - 1][i] != -1)
liftSmall[l][i] = liftSmall[l - 1][liftSmall[l - 1][i]];
//liftBig[0][0] = -1;
for(int i = 0; i < _N; i++)
for(auto it : dsuBig[i])
liftBig[0][it] = i;
for(int l = 1; l <= LOGMAX; l++)
for(int i = 0; i < _N; i++)
if(liftBig[l - 1][i] != -1)
liftBig[l][i] = liftBig[l - 1][liftBig[l - 1][i]];
/*
std::cout << liftSmall[0][1] << ' ' << liftSmall[1][1] << ' ' << liftSmall[2][1] << ' ' << liftSmall[3][1] << '\n';
std::cout << liftSmall[1][0] << ' ' << liftSmall[2][3] << '\n';
std::cout << liftBig[0][2] << ' ' << liftBig[1][2] << '\n';
std::cout << liftBig[1][4] << ' ' << liftBig[5][4] << '\n';
*/
}
struct Query {
int l1, r1, l2, r2;
int index;
};
std::vector < Query > queries;
int StoreQuery(int st, int en, int L, int R, int index) {
///All nodes reach-able from st, >= L
int rootBig = st;
for(int l = LOGMAX; l >= 0; l--)
if(liftBig[l][rootBig] != -1 && liftBig[l][rootBig] >= L) {
rootBig = liftBig[l][rootBig];
}
///All nodes reach-able from en, <= R
int rootSmall = en;
for(int l = LOGMAX; l >= 0; l--)
if(liftSmall[l][rootSmall] != -1 && liftSmall[l][rootSmall] <= R) {
rootSmall = liftSmall[l][rootSmall];
}
queries.push_back({lfSmall[rootSmall], rgSmall[rootSmall], lfBig[rootBig], rgBig[rootBig], index});
/*
std::cout << "Nodes reach-able from " << st << " with >= " << L << '\n';
dfsBig(rootBig);
std::cout << "---\n";
std::cout << "Nodes reach-able from " << en << " with <= " << R << '\n';
dfsSmall(rootSmall);
std::cout << "---\n";
*/
return 1;
}
int posTourSmall[NMAX + 2], posTourBig[NMAX + 2];
int matchBig[NMAX + 2];
struct SegmentTree {
std::set <int> v[4 * NMAX];
void Build(int node, int st, int dr) {
if(st == dr) {
v[node].insert(matchBig[st]);
return;
}
int mid = (st + dr) >> 1;
Build(2 * node, st, mid);
Build(2 * node + 1, mid + 1, dr);
for(auto it : v[2 * node])
v[node].insert(it);
for(auto it : v[2 * node + 1])
v[node].insert(it);
}
bool Query(int node, int st, int dr, int L, int R, int L2, int R2) {
if(R < st || L > dr)
return false;
if(L <= st && dr <= R) {
auto p = v[node].lower_bound(L2);
if(p != v[node].end() && *p <= R2)
return true;
return false;
}
int mid = (st + dr) >> 1;
bool ans1 = Query(2 * node, st, mid, L, R, L2, R2);
bool ans2 = Query(2 * node + 1, mid + 1, dr, L, R, L2, R2);
return ans1 | ans2;
}
};
SegmentTree sg;
void BuildSegmentTree() {
for(int i = 0; i < _N; i++) {
//posTourSmall[tourSmall[i]] = i;
posTourBig[tourBig[i]] = i;
}
for(int i = 0; i < _N; i++) {
matchBig[i] = posTourBig[tourSmall[i]];
}
/*
std::cout << "Tour small:\n";
for(auto it : tourSmall)
std::cout << it << ' ';
std::cout << "\nTour big:\n";
for(auto it : tourBig)
std::cout << it << ' ';
std::cout << "\nMatch big:\n";
for(int i = 0; i < _N; i++)
std::cout << matchBig[i] << ' ';
std::cout << "\n\n\n";
*/
sg.Build(1, 0, _N - 1);
}
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 = (int)X.size();
for(int i = 0; i < M; i++) {
g[X[i]].push_back(Y[i]);
g[Y[i]].push_back(X[i]);
}
BuildDSUs();
PrecomputeLift();
BuildSegmentTree();
Q = (int)S.size();
for (int i = 0; i < Q; ++i) {
StoreQuery(S[i], E[i], L[i], R[i], i);
}
/*
for (int i = 0; i < Q; ++i) {
std::cout << "Query " << queries[i].index << ' ' << queries[i].l1 << ' ' << queries[i].r1 << ' ' << queries[i].l2 << ' ' << queries[i].r2 << '\n';
}
*/
std::vector<int> A(Q);
for(int i = 0; i < Q; ++i) {
A[i] = sg.Query(1, 0, _N - 1, queries[i].l1, queries[i].r1, queries[i].l2, queries[i].r2);
}
return A;
}
