#include "werewolf.h"
#include<bits/stdc++.h>
using namespace std;
typedef pair<int,int> pii;
typedef vector<int> vi;
#define all(x) x.begin(), x.end()
#define sz(x) (int)x.size()
#define mk make_pair
#define pb push_back
#define fr first
#define sc second
vi pai, euler, tin, tout;
vector<vi> lift, edges;
int find(int x) {
if(pai[x] == x) return x;
return pai[x] = find(pai[x]);
}
void join(int x, int y) {
x = find(x);
y = find(y);
if(x == y) return;
pai[x] = y;
edges[y].pb(x);
}
void dfs(int x) {
euler.pb(x);
tin[x] = sz(euler) - 1;
for(auto viz : edges[x])
lift[0][viz] = x, dfs(viz);
tout[x] = sz(euler) - 1;
}
void construct_graph(int N, vector<pii> ord) {
pai.resize(N);
edges.clear();
edges.resize(N);
for(int i = 0; i < N; i++) pai[i] = i;
for(auto [a,b] : ord) join(b, a); // a <- b
euler.clear();
tin.resize(N);
tout.resize(N);
lift.resize(20, vi(N+1));
lift[0][ord.back().fr] = lift[0][N] = N;
dfs(ord.back().fr);
for(int b = 1; b < 20; b++)
for(int i = 0; i <= N; i++)
lift[b][i] = lift[b-1][lift[b-1][i]];
}
vi l, r, a, b; // ind, l, r, a, b
vi seg;
void update(int node, int ll, int rr, int val, int pos) {
seg[node] = max(seg[node], val);
if(ll == rr) return;
int mid = (ll+rr)/2;
if(pos <= mid) update(2*node, ll, mid, val, pos);
else update(2*node+1, mid+1, rr, val, pos);
}
int query(int node, int ll, int rr, int p, int q) {
if(rr < p or q < ll) return -1;
if(p <= ll and rr <= q) return seg[node];
int mid = (ll+rr)/2;
return max(query(2*node, ll, mid, p, q), query(2*node+1, mid+1, rr, p, q));
}
vi solve(vi V) {
int N = sz(V), Q = sz(l);
vi ans(Q), pos(N);
vector<vi> qq(N);
seg.resize(4*N, -1);
for(int i = 0; i < N; i++) pos[V[i]] = i;
for(int i = 0; i < Q; i++)
qq[b[i]].pb(i);
for(int i = 0; i < N; i++) {
update(1, 0, N-1, i, pos[i]);
for(auto it : qq[i])
if(query(1, 0, N-1, l[it], r[it]) >= a[it]) ans[it] = 1;
}
return ans;
}
vi check_validity(int N, vi X, vi Y, vi S, vi E, vi L, vi R) {
int M = sz(X), Q = sz(S);
vector<pii> ord;
l.resize(Q);
r.resize(Q);
a.resize(Q);
b.resize(Q);
// primeiro grafo
for(int i = 0; i < M; i++) ord.pb({min(X[i], Y[i]), max(X[i], Y[i])});
sort(all(ord));
reverse(all(ord));
construct_graph(N, ord);
vi V = euler;
for(int i = 0; i < Q; i++) {
for(int b = 19; b >= 0; b--)
if(lift[b][S[i]] >= L[i] and lift[b][S[i]] != N)
S[i] = lift[b][S[i]];
l[i] = tin[S[i]];
r[i] = tout[S[i]];
}
// segundo grafo
for(int i = 0; i < M; i++) swap(ord[i].fr, ord[i].sc);
sort(all(ord));
construct_graph(N, ord);
vi C(N);
for(int i = 0; i < N; i++) C[euler[i]] = i;
for(int i = 0; i < Q; i++) {
for(int b = 19; b >= 0; b--)
if(lift[b][E[i]] <= R[i]) E[i] = lift[b][E[i]];
a[i] = tin[E[i]];
b[i] = tout[E[i]];
}
// construir vetor e resolver o novo problema
for(int i = 0; i < N; i++) V[i] = C[V[i]];
return solve(V);
}
