#include "werewolf.h"
#include <bits/stdc++.h>
using namespace std;
const long long MAXN=400009;
int mas[MAXN];
bool done[MAXN];
int ansToQ[MAXN][2];
vector<pair<int,int>> edg;
vector<int> A;
struct Query
{
int num,l,r,id,bl;
};
vector<Query> queries;
bool sorter(Query& a,Query& b)
{
return a.num<b.num;
}
inline int min1(int a,int b)
{
if(a>b)return b;
return a;
}
inline int max1(int a,int b)
{
if(a<b)return b;
return a;
}
struct Fenwick
{
int fen[MAXN];
int lp2(int a)
{
return a&(-a);
}
void change(int a)
{
while(a<MAXN)
{
fen[a]++;
a+=lp2(a);
}
}
int getAns(int a)
{
int ans=0;
while(a>0)
{
ans+=fen[a];
a-=lp2(a);
}
return ans;
}
int query(int l,int r)
{
return getAns(r)-getAns(l-1);
}
};
struct Tree
{
int eulT[MAXN];
int father[MAXN],fatherDSU[MAXN],nodeEdg[MAXN],dist[MAXN],posEul[MAXN];
int dp[MAXN][35];
int sons[MAXN][2];
pair<int,int> range[MAXN];
int N,curr;
int Lead(int a)
{
if(fatherDSU[a]==a)return a;
return fatherDSU[a]=Lead(fatherDSU[a]);
}
pair<int,int> dfs(int start,int d)
{
dist[start]=d;
if(start<=N)
{
posEul[start]=curr;
eulT[curr]=start;
range[start]={curr,curr};
curr++;
return range[start];
}
range[start]= {dfs(sons[start][0],d+1).first,dfs(sons[start][1],d+1).second};
return range[start];
}
long long f(int n,int p)
{
if(dp[n][p]!=0)return dp[n][p];
if(p==0)return father[n];
return dp[n][p]=f(f(n,p-1),p-1);
}
int lca(int a,int b)
{
if(dist[a]>dist[b])swap(a,b);
for(int i=0; i<30; i++)
{
if((dist[b]-dist[a])&(1LL<<i))b=f(b,i);
}
if(a==b)return a;
for(int i=30; i>=0; i--)
{
if(f(a,i)!=f(b,i))
{
a=f(a,i);
b=f(b,i);
}
}
return father[a];
}
pair<int,int> findRange(int n,int wei,bool big)
{
if(big)
{
for(int i=32;i>=0;i--)
{
if(nodeEdg[f(n,i)]<=wei)n=f(n,i);
}
}
else
{
for(int i=32;i>=0;i--)
{
if(nodeEdg[f(n,i)]>=wei)n=f(n,i);
}
}
return range[n];
}
void build(int n,vector<pair<int,int>> edg,bool big)
{
N=n;
curr=N+1;
for(int i=1;i<=N;i++)
{
nodeEdg[i]=i;
fatherDSU[i]=i;
}
for(auto i:edg)
{
if(Lead(i.first)==Lead(i.second))continue;
if(big)nodeEdg[curr]=max1(nodeEdg[Lead(i.first)],nodeEdg[Lead(i.second)]);
else nodeEdg[curr]=min1(nodeEdg[Lead(i.first)],nodeEdg[Lead(i.second)]);
sons[curr][0]=Lead(i.first);
sons[curr][1]=Lead(i.second);
father[curr]=curr;
fatherDSU[curr]=curr;
father[Lead(i.first)]=curr;
fatherDSU[Lead(i.first)]=curr;
father[Lead(i.second)]=curr;
fatherDSU[Lead(i.second)]=curr;
curr++;
}
curr=1;
dfs(2*N-1,0);
}
};
Tree treeMax,treeMin;
Fenwick fenTree;
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 M=X.size(),Q=S.size();
pair<int,int> x,y;
for(int i=0;i<M;i++)
{
X[i]++;
Y[i]++;
if(X[i]<Y[i])swap(X[i],Y[i]);
edg.push_back({X[i],Y[i]});
}
sort(edg.begin(),edg.end());
treeMax.build(N,edg,1);
for(int i=0;i<M;i++)
{
swap(edg[i].first,edg[i].second);
}
sort(edg.begin(),edg.end());
reverse(edg.begin(),edg.end());
treeMin.build(N,edg,0);
for(int i=1;i<=N;i++)
{
mas[treeMax.posEul[treeMin.eulT[i]]]=i;
}
for(int i=1;i<=N;i++)cout<<mas[i]<<" ";
cout<<endl<<endl;
for(int i=0;i<Q;i++)
{
S[i]++;
E[i]++;
L[i]++;
R[i]++;
if(S[i]<L[i]||E[i]>R[i])
{
done[i]=1;
A.push_back(0);
continue;
}
x=treeMin.findRange(S[i],L[i],0);
y=treeMax.findRange(E[i],R[i],1);
queries.push_back({y.first-1,x.first,x.second,i,0});
queries.push_back({y.second,x.first,x.second,i,1});
}
sort(queries.begin(),queries.end(),sorter);
/*
for(auto i:queries)
{
int ans=0;
for(int j=1;j<=i.num;j++)
{
ans+=(mas[j]>=i.l&&mas[j]<=i.r);
}
ansToQ[i.id][i.bl]=ans;
}
*/
int curr=0;
for(int i=1;i<=N;i++)
{
fenTree.change(mas[i]);
while(curr<queries.size()&&queries[curr].num<=i)
{
if(queries[curr].num==0)
{
curr++;
continue;
}
//cout<<i<<" "<<queries[curr].num<<" "<<fenTree.query(1,N)<<endl;
ansToQ[queries[curr].id][queries[curr].bl]=fenTree.query(queries[curr].l,queries[curr].r);
curr++;
}
}
for(int i=0;i<Q;i++)
{
if(done[i])continue;
//cout<<ansToQ[i][0]<<" "<<ansToQ[i][1]<<endl;
A.push_back(1-bool(ansToQ[i][0]==ansToQ[i][1]));
}
return A;
}
