#include "werewolf.h"
#include<bits/stdc++.h>
using namespace std;
const int nmax=4e5+42;
struct edge
{
int u,v,cost;
};
edge all[nmax];
bool cmp_1(edge a,edge b)
{
return a.cost<b.cost;
}
bool cmp_2(edge a,edge b)
{
return a.cost>b.cost;
}
int parent[nmax];
int root(int node)
{
if(parent[node]==node)return node;
parent[node]=root(parent[node]);
return parent[node];
}
vector<int> seen[nmax];
int le[nmax],ri[nmax];
void my_merge(int u,int v)
{
u=root(u);
v=root(v);
if(u==v)return;
//cout<<"my_merge "<<u<<" "<<v<<endl;
if(seen[u].size()<seen[v].size())swap(u,v);
for(auto k:seen[v])
seen[u].push_back(k);
le[u]=min(le[u],le[v]);
ri[u]=max(ri[u],ri[v]);
parent[v]=u;
}
int order_mini[nmax],order_maxi[nmax];
vector< pair<int,int> > queries[nmax];
pair<int,int> mem_mini[nmax],mem_maxi[nmax];
int where[nmax];
pair<int,int> points[nmax];
struct rect
{
int x1,y1,x2,y2,id;
};
rect help[nmax];
bool cmp_rect(rect a,rect b)
{
return a.x2<b.x2;
}
int tree[4*nmax];
void update(int node,int l,int r,int pos,int val)
{
tree[node]=max(tree[node],val);
if(l==r)return;
int av=(l+r)/2;
if(pos<=av)update(node*2,l,av,pos,val);
else update(node*2+1,av+1,r,pos,val);
}
int query(int node,int l,int r,int lq,int rq)
{
if(l==lq&&r==rq)return tree[node];
int av=(l+r)/2,ret=-1;
if(lq<=av)ret=max(ret,query(node*2,l,av,lq,min(av,rq)));
if(av<rq)ret=max(ret,query(node*2+1,av+1,r,max(av+1,lq),rq));
return ret;
}
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 M=X.size();
//min tree
for(int i=0;i<M;i++)
{
all[i].u=X[i];
all[i].v=Y[i];
all[i].cost=max(X[i],Y[i]);
}
for(int i=0;i<N;i++)parent[i]=i;
sort(all,all+M,cmp_1);
for(int i=0;i<N;i++)seen[i]={i};
for(int i=0;i<M;i++)
{
my_merge(all[i].u,all[i].v);
/*
for(int j=0;j<N;j++)
{
cout<<j<<" -> "<<root(j)<<" : ";for(auto k:seen[j])cout<<k<<" ";cout<<endl;
}
*/
}
for(int i=0;i<N;i++)
{
order_mini[i]=seen[root(0)][i];
le[order_mini[i]]=i;
ri[order_mini[i]]=i;
//cout<<i<<" -> "<<order_mini[i]<<endl;
}
for(int i=0;i<L.size();i++)
queries[R[i]].push_back({E[i],i});
for(int i=0;i<N;i++)parent[i]=i;
for(int i=0;i<N;i++)seen[i]={};
int pointer=0;
for(int t=0;t<N;t++)
{
while(pointer<M&&all[pointer].cost==t)
{
my_merge(all[pointer].u,all[pointer].v);
pointer++;
}
for(auto k:queries[t])
{
mem_mini[k.second]={le[root(k.first)],ri[root(k.first)]};
}
}
//max tree
for(int i=0;i<M;i++)
{
all[i].u=X[i];
all[i].v=Y[i];
all[i].cost=min(X[i],Y[i]);
}
for(int i=0;i<N;i++)parent[i]=i;
sort(all,all+M,cmp_2);
for(int i=0;i<N;i++)seen[i]={i};
for(int i=0;i<M;i++)
my_merge(all[i].u,all[i].v);
for(int i=0;i<N;i++)
{
order_maxi[i]=seen[root(0)][i];
le[order_maxi[i]]=i;
ri[order_maxi[i]]=i;
//cout<<i<<" -> "<<order_maxi[i]<<endl;
}
for(int i=0;i<N;i++)
queries[i]={};
for(int i=0;i<R.size();i++)
queries[L[i]].push_back({S[i],i});
for(int i=0;i<N;i++)parent[i]=i;
for(int i=0;i<N;i++)seen[i]={};
pointer=0;
for(int t=N-1;t>=0;t--)
{
while(pointer<M&&all[pointer].cost==t)
{
my_merge(all[pointer].u,all[pointer].v);
pointer++;
}
for(auto k:queries[t])
{
mem_maxi[k.second]={le[root(k.first)],ri[root(k.first)]};
}
}
for(int i=0;i<N;i++)
{
where[order_mini[i]]=i;
}
for(int i=0;i<N;i++)
{
points[i]={where[order_maxi[i]],i};
//cout<<points[i].first<<" "<<points[i].second<<endl;
}
sort(points,points+N);
for(int i=0;i<L.size();i++)
{
help[i].x1=mem_mini[i].first;
help[i].x2=mem_mini[i].second;
help[i].y1=mem_maxi[i].first;
help[i].y2=mem_maxi[i].second;
//cout<<i<<" -> "<<help[i].x1<<" "<<help[i].y1<<" "<<help[i].x2<<" "<<help[i].y2<<endl;
help[i].id=i;
}
sort(help,help+L.size(),cmp_rect);
memset(tree,-1,sizeof(tree));
vector<int> ret(L.size(),0);
int pointer_points=0,pointer_queries=0;
for(int x=0;x<N;x++)
{
while(pointer_points<N&&points[pointer_points].first==x)
{
update(1,0,N-1,points[pointer_points].second,points[pointer_points].first);
//cout<<"update "<<points[pointer_points].second<<" with "<<points[pointer_points].first<<endl;
pointer_points++;
}
//for(int j=0;j<N;j++)cout<<j<<" -> "<<query(1,0,N-1,j,j)<<endl;
while(pointer_queries<L.size()&&help[pointer_queries].x2==x)
{
ret[help[pointer_queries].id]=(query(1,0,N-1,help[pointer_queries].y1,help[pointer_queries].y2)>=help[pointer_queries].x1);
//cout<<query(1,0,N-1,help[pointer_queries].y1,help[pointer_queries].y2)<<" wanted "<<help[pointer_queries].x1<<endl;
pointer_queries++;
}
//cout<<"---"<<endl;
}
return ret;
}
