#include "werewolf.h"
#include <vector>
#include <utility>
#include <algorithm>
#define MAXN 200005
using namespace std;
class DSU { //1 indexed
int par[MAXN], sz;
vector<int> T[MAXN];
public:
int anc[MAXN][20], ID[MAXN][2], seq = 1;
int Find(int x) {
return(par[x] == x ? x : par[x] = Find(par[x]));
}
void Union(int x, int y) {
int p1 = Find(x), p2 = Find(y);
if (p1 == p2) {return;}
if (!anc[p1][0]) {
anc[p1][0]=p2;
T[p2].push_back(p1);
}
par[p1]=p2;
}
void Init(int n) {
sz = n;
for (int i=1; i <= n; i++) {
par[i]=i;
}
}
void makeJump() {
for (int i=1; i<20; i++) {
for (int j=1; j<=sz; j++) {
anc[j][i] = anc[anc[j][i-1]][i-1];
}
}
}
void ET(int u) {
ID[u][0] = seq;
seq++;
for (auto v: T[u]) {ET(v);}
ID[u][1] = seq - 1;
}
int range(int v, int cap, bool t) { //t = 1 means all values at most cap
for (int i=19; i>=0; i--) { //t = 0 means all values at least cap
if (t && anc[v][i] && anc[v][i] <= cap) {
v = anc[v][i];
} else if ((!t) && anc[v][i] && anc[v][i] >= cap) {
v = anc[v][i];
}
}
if (t && anc[v][0] && anc[v][0] <= cap) {
v = anc[v][0];
} else if ((!t) && anc[v][0] && anc[v][0] >= cap) {
v = anc[v][0];
}
return(v);
}
} Tmin, Tmax; //semi-Kruskal reconstruction trees: doesn't need to add new node
class PersistentSegtree {
int ST[MAXN * 30][3];
int R[MAXN], X[MAXN], pt = 1, ver = 1;
public:
int upd(int ind, int l, int r, int cur) {
if (ind < l || ind > r) {return(cur);}
if (l == r) {
ST[pt][0] = ST[cur][0] + 1, pt++;
return(pt-1);
} else {
int tmp = pt, mid = (l + r) >> 1;
pt++;
ST[tmp][1] = upd(ind, l, mid, ST[cur][1]);
ST[tmp][2] = upd(ind, mid+1, r, ST[cur][2]);
ST[tmp][0] = ST[ST[tmp][1]][0] + ST[ST[tmp][2]][0];
return(tmp);
}
}
int ask(int lo, int hi, int l, int r, int cur) {
if (hi < l || lo > r || !cur) {return(0);}
if (lo <= l && hi >= r) {return(ST[cur][0]);}
else {
int mid = (l + r) >> 1;
return(ask(lo, hi, l, mid, ST[cur][1]) +
ask(lo, hi, mid+1, r, ST[cur][2]));
}
}
void add(int x, int y) {
X[ver] = x;
R[ver] = upd(y, 1, MAXN, R[ver-1]);
ver++;
}
int get(int x) { //find largest index i that X[i] not exceeding x
int lo = 0, hi = ver;
while (lo + 1 != hi) {
int mid = (lo + hi) >> 1;
if (X[mid] <= x) {lo = mid;}
else {hi = mid;}
}
return(lo);
}
int Sum(int xlo, int ylo, int xhi, int yhi) {
int ql = get(xlo) - 1, qr = get(xhi);
return(ask(ylo, yhi, 1, MAXN, R[qr]) - ask(ylo, yhi, 1, MAXN, R[ql]));
}
} PST;
vector<int> adj[MAXN];
vector<pair<int,int> > pts;
vector<int> check_validity(int N, vector<int> X, vector<int> Y,
vector<int> S, vector<int> E,
vector<int> L, vector<int> R) {
int Q = S.size(), M = X.size();
Tmin.Init(N), Tmax.Init(N);
for (int i=0; i<M; i++) {
adj[X[i]+1].push_back(Y[i]+1);
adj[Y[i]+1].push_back(X[i]+1);
}
for (int i=1; i<=N; i++) { //min bottleneck (minimise max wt)
for (auto v: adj[i]) {
if (i > v) {
Tmin.Union(v,i);
}
}
}
for (int i=N; i>=1; i--) { //max bottleneck (max min wt)
for (auto v: adj[i]) {
if (i < v) {
Tmax.Union(v,i);
}
}
}
Tmin.ET(N), Tmax.ET(1);
Tmin.makeJump(), Tmax.makeJump();
for (int i=1; i<=N; i++) {
pts.push_back({Tmin.ID[i][0], Tmax.ID[i][0]});
}
sort(pts.begin(), pts.end());
for (auto P: pts) {
PST.add(P.first, P.second);
}
vector<int> A;
for (int i = 0; i < Q; ++i) {
int s = S[i] + 1, e = E[i] + 1, l = L[i] + 1, r = R[i] + 1;
int s2 = Tmax.range(s, l, false), e2 = Tmin.range(e, r, true);
int xl = Tmin.ID[e2][0], xr = Tmin.ID[e2][1];
int yl = Tmax.ID[s2][0], yr = Tmax.ID[s2][1];
if (PST.Sum(xl, yl, xr, yr)) {A.push_back(1);}
else {A.push_back(0);}
}
return A;
}
