#include<iostream>
#include<vector>
#include<tuple>
#include "werewolf.h"
using namespace std;
const int MAX_N=2e5+5;
const int MAX_M=4e5+5;
const int BLOCK_SIZE=1500;
int n,m,q;
vector<int>g[MAX_N];
struct qq
{
int l,r,s,e,id;
};
vector<qq>forleft[MAX_N],forright[MAX_N],queries;
vector<tuple<int,int,int>>checkone[MAX_N];
int pare[MAX_N];
///init
vector<pair<int,int>>updates[MAX_N];
int prevblockcnt[MAX_N];
vector<tuple<int,int,int>>blockqueries[MAX_N];
///blocks
int parent[MAX_N],sz[MAX_N];
int curtime;
int Find(int u)
{
if(parent[u]==u)return u;
return parent[u]=Find(parent[u]);
}
void Merge(int u,int v,bool f)
{
int urt=Find(u),vrt=Find(v);
if(urt==vrt)return;
if(sz[urt]>sz[vrt])swap(urt,vrt);
parent[urt]=vrt;
sz[vrt]+=sz[urt];
if(!f)return;
for(auto [node,useless]:updates[urt])
{
updates[vrt].push_back({node,curtime});
}
}
///dsu
void Update(qq query)
{
int node=pare[query.id];
int posr,br;
int l=0,r=updates[node].size()-1;
while(l<=r)
{
int mid=(l+r)/2;
if(updates[node][mid].second<=query.r)
{
posr=mid;
l=mid+1;
}
else r=mid-1;
}
br=posr/BLOCK_SIZE;
for(int b=0;b<br;b++)
{
blockqueries[prevblockcnt[node]+b+1].push_back({query.l,query.s,query.id});
}
for(int i=br*BLOCK_SIZE;i<=posr;i++)
{
checkone[query.l].push_back({updates[node][i].first,query.s,query.id});
}
}
vector<int>nodes;
vector<int>ans;
bool active[MAX_N];
bool used[MAX_N];
void dfs(int u)
{
used[u]=1;
for(int v:g[u])
{
if(v>=curtime && !used[v])dfs(v);
}
}
void bfs(int block)
{
int idxqueries=0;
for(int i=0;i<n;i++)used[i]=0;
for(int i=n-1;i>=0;i--)
{
while(idxqueries+1<blockqueries[block].size() && get<0>(blockqueries[block][idxqueries])>i)idxqueries++;
if(active[i])used[i]=1;
for(int v:g[i])
{
if(v>i)
{
if(used[v]==used[i])continue;
curtime=i;
if(used[i])dfs(v);
else dfs(i);
}
}
if(i==get<0>(blockqueries[block][idxqueries]))
{
if(used[get<1>(blockqueries[block][idxqueries])])
{
ans[get<2>(blockqueries[block][idxqueries])]=1;
}
}
}
for(int u:nodes)active[u]=0;
nodes.clear();
}
void solve()
{
for(int i=0;i<n;i++)
{
parent[i]=i;
sz[i]=i;
}
updates[0].push_back({0,0});
for(int i=1;i<n;i++)
{
curtime=i;
updates[i].push_back({i,i});
for(int v:g[i])
{
if(v<i)
{
Merge(v,i,1);
}
}
for(auto query:forright[i])
{
pare[query.id]=Find(query.e);
}
}
int curblockcnt=0;
for(int i=0;i<=n;i++)
{
prevblockcnt[i]=curblockcnt;
curblockcnt+=updates[i].size()/BLOCK_SIZE;
}
for(int i=n-1;i>=0;i--)
{
for(auto query:forleft[i])Update(query);
}
///make queries
int block=1;
for(int i=0;i<n;i++)
{
int posl=0,posr=BLOCK_SIZE-1;
while(posr<updates[i].size())
{
if(blockqueries[block].size()>0)
{
for(int j=posl;j<=posr;j++)
{
nodes.push_back(updates[i][j].first);
active[updates[i][j].first]=1;
}
bfs(block);
}
block++;
posl+=BLOCK_SIZE;
posr+=BLOCK_SIZE;
}
}
//block queries
for(int i=0;i<n;i++)
{
parent[i]=i;
sz[i]=i;
}
for(int i=n-1;i>=0;i--)
{
for(int v:g[i])
{
if(v>i)
{
Merge(v,i,0);
}
}
for(auto que:checkone[i])
{
int u,v,id;
tie(u,v,id)=que;
if(Find(u)==Find(v))ans[id]=1;
}
}
//single node queries
///solve queries
}
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=X.size();
for(int i=0;i<m;i++)
{
int u=X[i],v=Y[i];
g[u].push_back(v);
g[v].push_back(u);
}
q=S.size();
ans.resize(q);
for(int i=0;i<q;i++)
{
qq cur;cur.s=S[i];cur.e=E[i];cur.l=L[i];cur.r=R[i];cur.id=i;
forleft[L[i]].push_back(cur);
forright[R[i]].push_back(cur);
queries.push_back(cur);
}
solve();
return ans;
}
