#include "werewolf.h"
#include <bits/stdc++.h>
using namespace std;
#define fo(i,s,t) for(int i = s; i <= t; ++ i)
#define fd(i,s,t) for(int i = s; i >= t; -- i)
#define bf(i,s) for(int i = head[s]; i; i = e[i].next)
#define mp make_pair
#define fi first
#define se second
#define pii pair<int,int>
#define pb push_back
#define VI vector<int>
#define sf scanf
#define pf printf
#define fp freopen
#define SZ(x) ((int)(x).size())
#ifdef MPS
#define D(x...) printf(x)
#else
#define D(x...)
#endif
typedef long long ll;
typedef double db;
typedef unsigned long long ull;
const int inf = 1<<30;
const ll INF = 1ll<<60;
const db Inf = 1e20;
const db eps = 1e-9;
const int maxn = 200050;
int fa[maxn];
struct KruskalT
{
VI adj[maxn];
int tot, anc[maxn][20], in[maxn], out[maxn];
void link(int u, int v)
{
adj[u].emplace_back(v);
anc[v][0] = u;
}
void init(int N)
{
fo(j,1,19)
for(int i = 0; i < N; ++ i)
if(anc[i][j-1] != -1)
anc[i][j] = anc[anc[i][j-1]][j-1];
}
int getsub(int u, int x, int oper) // oper = 0 => >= L[i], 1-> <=R[i]
{
if(oper == 0)
{
fd(i,19,0)
if(anc[u][i] != -1 && anc[u][i] >= x)
u = anc[u][i];
if(u >= x) return u;
else return -1;
}
else
{
fd(i,19,0)
if(anc[u][i] != -1 && anc[u][i] <= x)
u = anc[u][i];
if(u <= x) return u;
else return -1;
}
}
void dfs(int u)
{
in[u] = ++ tot;
for(auto p : adj[u]) dfs(p);
out[u] = tot;
}
}Tu, Tv, T;
int ls[maxn*20], rs[maxn*20], nd[maxn*20], tot;
int rt[maxn], bag[maxn];
int getfa(int x){return fa[x] == x ? x : fa[x] = getfa(fa[x]);}
void add(int &now, int pre, int p, int l, int r)
{
now = ++ tot;
nd[now] = nd[pre] + 1; ls[now] = ls[pre]; rs[now] = rs[pre];
if(l == r) return;
int mid = l + r >> 1;
if(p <= mid) add(ls[now], ls[pre], p, l, mid);
else add(rs[now], rs[pre], p, mid+1, r);
}
int ask(int now, int pre, int l, int r, int L, int R)
{
if(!now) return 0;
if(l <= L && R <= r) return nd[now] - nd[pre];
int mid = L + R >> 1;
if(r <= mid) return ask(ls[now], ls[pre], l, r, L, mid);
else if(l > mid) return ask(rs[now], rs[pre], l, r, mid+1, R);
else return ask(ls[now], ls[pre], l, mid, L, mid) +
ask(rs[now], rs[pre], mid+1, r, mid+1, R);
}
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) {
int Q = S.size(), M = X.size();
std::vector<int> A(Q);
// construct two trees
for(int i = 0; i < N; ++ i) fa[i] = i;
memset(Tu.anc,0xff,sizeof(Tu.anc));
memset(Tv.anc,0xff,sizeof(Tv.anc));
for(int i = 0; i < M; ++ i) T.link(X[i], Y[i]), T.link(Y[i], X[i]);
for(int i = N-1; i >= 0; -- i)
{
for(auto p : T.adj[i]) if(p > i)
{
int fx = getfa(p);
if(fx != i) {fa[fx] = i; Tu.link(i, fx); D("%d %d\n",i,fx);}
}
}
D("~~~~~~~~~~\n");
for(int i = 0; i < N; ++ i) fa[i] = i;
for(int i = 0; i < N; ++ i)
{
for(auto p : T.adj[i]) if(p < i)
{
int fx = getfa(p);
if(fx != i) {fa[fx] = i; Tv.link(i, fx); D("%d %d\n",i,fx);}
}
}
D("~~~~~~~~~\n");
//build up binary lifting stuffs
Tu.init(N); Tv.init(N);
Tu.dfs(0); Tv.dfs(N-1);
//insert points into persistent rangetree
for(int i = 0; i < N; ++ i)
bag[Tu.in[i]] = Tv.in[i];
for(int i = 1; i <= Tu.tot; ++ i)
{
add(rt[i], rt[i-1], bag[i], 1, Tv.tot);
D("%d\n",ask(rt[i],rt[i-1],bag[i],bag[i],1,Tv.tot));
}
//now query
for(int i = 0; i < Q; ++ i)
{
int x = Tu.getsub(S[i], L[i], 0), y = Tv.getsub(E[i], R[i], 1);
if(x == -1 || y == -1) {A[i] = 0; continue;}
D("%d %d %d\n",i,x,y);
D("[%d,%d] [%d,%d]\n",Tu.in[x],Tu.out[x],Tv.in[y],Tv.out[y]);
A[i] = ask(rt[Tu.out[x]], rt[Tu.in[x]-1], Tv.in[y], Tv.out[y], 1, Tv.tot);
A[i] = (A[i] > 0);
}
return A;
}
