#include "werewolf.h"
#include <iostream>
#include <algorithm>
#include <vector>
using namespace std;
const int N=1e6+100,LG=20;
int tin1[N],tout1[N],par1[N][LG];
int par[N][LG],inv[N],pr[N],tin[N],tout[N],val[N],vals[N],tmp=0;
vector<int> ma[N],sf[N];
int get(int x)
{
return (pr[x]==x)?x:pr[x]=get(pr[x]);
}
void dfs(int x,int p=0)
{
par[x][0]=p;
for(int j=1;j<LG;j++)par[x][j]=par[par[x][j-1]][j-1];
tin[x]=++tmp;
for(auto y:sf[x])
{
dfs(y,x);
}
tout[x]=tmp;
// cout<<"Suffix tree "<<x<<' '<<tin[x]<<' '<<tout[x]<<endl;
}
void dfs1(int x,int p=0)
{
par1[x][0]=p;
for(int j=1;j<LG;j++)par1[x][j]=par1[par1[x][j-1]][j-1];
tin1[x]=++tmp;
inv[tmp]=x;
for(auto y:sf[x])
{
dfs1(y,x);
}
tout1[x]=tmp;
// cout<<"Prefix tree "<<x<<' '<<tin1[x]<<' '<<tout1[x]<<endl;
}
int ogn,tt;
vector<int> cur[N<<1];
void build(int l=1,int r=tt,int v=1)
{
for(int k=l;k<=r;k++)
{
int x=inv[k];
if(1<=x and x<=ogn)
{
// cout<<"adding "<<x<<' '<<tin[x]<<" to range "<<l<<' '<<r<<endl;
cur[v].push_back(tin[x]);
}
}
sort(begin(cur[v]),end(cur[v]));
if(l==r)
{
return;
}
int m=(l+r)>>1,lc=v<<1,rc=lc|1;
build(l,m,lc);
build(m+1,r,rc);
}
bool count(int ql,int qr,int vl,int vr,int l=1,int r=tt,int v=1)
{
if(qr<l or r<ql)return 0;
if(ql<=l and r<=qr)
{
auto it=lower_bound(begin(cur[v]),end(cur[v]),vl);
// cout<<"finding "<<vl<<' '<<vr<<" in "<<ql<<' '<<qr<<endl;
// cout<<"cur "<<l<<' '<<r<<endl;
// for(auto x:cur[v])cout<<x<<' ';
// cout<<endl;
if(it!=end(cur[v]) and *it <= vr) return 1;
return 0;
}
// check if any element in range [ql,qr] is in the range [vl,vr]
int m=(l+r)>>1,lc=v<<1,rc=lc|1;
return count(ql,qr,vl,vr,l,m,lc)|count(ql,qr,vl,vr,m+1,r,rc);
}
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();
ogn=n;
tmp=0;
for(int i=0;i<=3*n;i++)
ma[i].clear(),pr[i]=i,sf[i].clear();
for(int i=0;i<X.size();i++)
{
X[i]++;
Y[i]++;
ma[X[i]].push_back(Y[i]);
ma[Y[i]].push_back(X[i]);
// cout<<X[i]<<' '<<Y[i]<<endl;
}
//
int nxt=n;
val[0]=-1e9;
// constructing the suffix tree
for(int p=n;p>=1;p--){
val[p]=-1e9;
// int ogp=p;
for(auto y:ma[p])
{
if(y>=p)
{
y=get(y);
int op=get(p);
if(y!=op)
{
nxt++;
// cout<<nxt<<' '<<y<<endl;
// cout<<nxt<<' '<<op<<endl;
sf[nxt].push_back(y);
sf[nxt].push_back(op);
pr[y]=nxt;
pr[op]=nxt;
val[nxt]=p;
}
}
}
}
// cout<<"ever ending "<<endl;
tmp=0;
dfs(nxt);
tt=nxt;
// making the prefix tree
for(int i=0;i<=3*n;i++)
pr[i]=i,sf[i].clear(),vals[i]=val[i];
nxt=n;
val[0]=1e9;
for(int p=1;p<=n;p++){
val[p]=1e9;
for(auto y:ma[p])
{
if(y<=p)
{
y=get(y);
int op=get(p);
if(y!=op)
{
nxt++;
// cout<<nxt<<' '<<y<<endl;
// cout<<nxt<<' '<<op<<endl;
sf[nxt].push_back(y);
sf[nxt].push_back(op);
pr[y]=nxt;
pr[op]=nxt;
val[nxt]=p;
}
}
}
}
// cout<<"prefix"<<endl;
tmp=0;
dfs1(nxt);
build();
vector<int> A(Q);
for (int i = 0; i < Q; ++i) {
int s=S[i]+1,e=E[i]+1,l=L[i]+1,r=R[i]+1;
// cout<<"query "<<i<<' '<<s<<' '<<e<<' '<<l<<' '<<r<<endl;
for(int j=LG-1;j>=0;j--)
{
if(vals[par[s][j]]>=l)
{
s=par[s][j];
}
if(val[par1[e][j]]<=r)
{
e=par1[e][j];
}
}
// cout<<"Ended up at "<<s<<' '<<e<<endl;
// cout<<val[s]<<' '<<vals[s]<<endl;
// cout<<val[e]<<' '<<vals[e]<<endl;
// cout<<tin1[e]<<' '<<tout1[e]<<endl;
// cout<<tin[s]<<' '<<tout[s]<<endl;
A[i]=count(tin1[e],tout1[e],tin[s],tout[s]);
// A[i]=(mi>=l or mx<=r);
}
return A;
}
