#include "werewolf.h"
#include<vector>
#include<algorithm>
using namespace std;
#define MAXN 200005
#define fi first
#define se second
typedef pair<int, int> pi;
struct tree{
int c[2*MAXN], par[20][2*MAXN], ro[2*MAXN], mn[2*MAXN], mx[2*MAXN];
vector<int> chi[2*MAXN];
int s[MAXN], sn;
int tn;
}tr[2];
int N, M;
vector<pi> e;
int seg[MAXN*4], G[MAXN][2];
bool cmp(pi a, pi b){
return max(a.fi, a.se)<max(b.fi, b.se);
}
int getro(tree* T, int x){
if(T->ro[x]==x) return x;
return T->ro[x]=getro(T, T->ro[x]);
}
void dfs(tree* T, int x){
if(x<N){
T->mn[x]=T->mx[x]=T->sn;
T->s[T->sn++]=x;
}
else{
T->mn[x]=N;
T->mx[x]=0;
for(auto a:T->chi[x]){
dfs(T, a);
T->mn[x]=min(T->mn[x], T->mn[a]);
T->mx[x]=max(T->mx[x], T->mx[a]);
}
}
}
void mktr(tree* T){
for(int i=0; i<N; i++) T->c[i]=T->ro[i]=T->mn[i]=T->mx[i]=i;
sort(e.begin(), e.end(), cmp);
T->tn=N;
for(auto a:e){
int r1=getro(T, a.fi), r2=getro(T, a.se);
if(r1!=r2){
T->par[0][r1]=T->par[0][r2]=T->par[0][T->tn]=T->ro[r1]=T->ro[r2]=T->ro[T->tn]=T->tn;
T->chi[T->tn].push_back(r1);
T->chi[T->tn].push_back(r2);
T->c[T->tn]=max(a.fi, a.se);
T->tn++;
}
}
for(int i=1; i<20; i++) for(int j=0; j<T->tn; j++) T->par[i][j]=T->par[i-1][T->par[i-1][j]];
T->sn=0;
dfs(T, T->tn-1);
}
int goup(tree* T, int x, int l){
for(int i=19; i>=0; i--) if(T->c[T->par[i][x]]<=l) x=T->par[i][x];
return x;
}
void updseg(int idx, int l, int r, int x){
seg[idx]++;
if(l<r){
int m=l+r>>1;
if(x<=m) updseg(idx*2, l, m, x);
else updseg(idx*2+1, m+1, r, x);
}
}
int gseg(int idx, int l, int r, int x, int y){
if(x<=l&&r<=y) return seg[idx];
if(r<x||y<l) return 0;
int m=l+r>>1;
return gseg(idx*2, l, m, x, y)+gseg(idx*2+1, m+1, r, x, y);
}
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();
vector<int> ans(Q);
vector<int> B[MAXN];
N=n;
M=X.size();
for(int i=0; i<M; i++) e.push_back(make_pair(N-X[i]-1, N-Y[i]-1));
mktr(&tr[0]);
for(int i=0; i<M; i++) e[i]=make_pair(X[i], Y[i]);
mktr(&tr[1]);
for(int i=0; i<Q; i++) G[i][0]=goup(&tr[0], N-S[i]-1, N-L[i]-1);
for(int i=0; i<Q; i++) G[i][1]=goup(&tr[1], E[i], R[i]);
for(int i=0; i<Q; i++){
if(tr[0].mn[G[i][0]]>0) B[tr[0].mn[G[i][0]]-1].push_back(i);
B[tr[0].mx[G[i][0]]].push_back(i);
}
for(int i=0; i<N; i++){
updseg(1, 0, N-1, tr[1].mx[N-tr[0].s[i]-1]);
for(auto a:B[i])
ans[a]+=(tr[0].mx[G[a][0]]==i?1:-1)*gseg(1, 0, N-1, tr[1].mn[G[a][1]], tr[1].mx[G[a][1]]);
}
for(int i=0; i<Q; i++) ans[i]=min(ans[i], 1);
return ans;
}
