#include "werewolf.h"
#include<bits/stdc++.h>
using namespace std;
int n;
struct qr{
int s,e,l,r,id;
qr(int _s,int _e,int _l,int _r,int _id){
s=_s,e=_e,l=_l,r=_r,id=_id;
}
};
struct dsu{
int p[400005];
int in[400005];
int out[400005];
int cur=0;
int tme=0;
vector<int>adj[400005];
void init(int n){
for(int i=1;i<=2*n;i++)p[i]=i;
cur=n;
}
int fp(int a){
if(p[a]==a)return a;
return p[a]=fp(p[a]);
}
void un(int a,int b){
a=fp(a),b=fp(b);
if(a==b)return;
cur++;
p[a]=cur;
p[b]=cur;
adj[cur].push_back(a);
adj[cur].push_back(b);
}
void dfs(int u){
in[u]=++tme;
for(auto x:adj[u])dfs(x);
out[u]=tme;
}
}pre,suf;
vector<pair<int,int>>pe[400005];
vector<pair<int,int>>se[400005];
int pqid[400005];
int sqid[400005];
int pl[400005];
int pr[400005];
int sl[400005];
int sr[400005];
vector<qr>pq[400005],sq[400005];
vector<int>pp[400005];
vector<pair<pair<int,int>,int>>add[400005];
vector<pair<pair<int,int>,int>>del[400005];
struct fenwick{
int info[400005];
void upd(int id,int val){
if(id==0)return;
for(int i=id;i<=2*n;i+=i&-i)info[i]+=val;
}
int fans(int id){
int ans=0;
for(int i=id;i>0;i-=i&-i)ans+=info[i];
return ans;
}
}fw;
vector<int> check_validity(int N, vector<int> X, vector<int> Y, vector<int> S, vector<int> E, vector<int> L, vector<int> R) {
n=N;
int Q = S.size();
int M= X.size();
vector<int> ans(Q);
for(int i=0;i<M;i++){
X[i]++,Y[i]++;
if(X[i]<Y[i])swap(X[i],Y[i]);
pe[X[i]].push_back({X[i],Y[i]});
se[Y[i]].push_back({X[i],Y[i]});
}
for(int i=0;i<Q;i++){
S[i]++,E[i]++,L[i]++,R[i]++;
auto temp=qr(S[i],E[i],L[i],R[i],i);
sq[L[i]].push_back(temp);
pq[R[i]].push_back(temp);
}
pre.init(N);
suf.init(N);
for(int i=1;i<=N;i++){
for(auto x:pe[i])pre.un(x.first,x.second);
for(auto x:pq[i])pqid[x.id]=pre.fp(x.e);
}
for(int i=N;i>=1;i--){
for(auto x:se[i])suf.un(x.first,x.second);
for(auto x:sq[i])sqid[x.id]=suf.fp(x.s);
}
pre.dfs(pre.fp(1));
suf.dfs(suf.fp(1));
for(int i=0;i<Q;i++){
pl[i]=pre.in[pqid[i]];
pr[i]=pre.out[pqid[i]];
sl[i]=suf.in[sqid[i]];
sr[i]=suf.out[sqid[i]];
//cerr<<"i:"<<i<<" "<<pl[i]<<" "<<pr[i]<<" "<<sl[i]<<" "<<sr[i]<<'\n';
del[pl[i]-1].push_back({{sl[i],sr[i]},i});
add[pr[i]].push_back({{sl[i],sr[i]},i});
}
for(int i=1;i<=N;i++){
int x=pre.in[i];
int y=suf.in[i];
//cerr<<"coord:"<<i<<' '<<x<<" "<<y<<"\n";
pp[x].push_back(y);
}
for(int i=1;i<=2*N;i++){
for(auto x:pp[i])fw.upd(x,1);
for(auto [x,id]:del[i])ans[id]-=fw.fans(x.second)-fw.fans(x.first-1);
for(auto [x,id]:add[i])ans[id]+=fw.fans(x.second)-fw.fans(x.first-1);
}
for(auto &x:ans)x=(x>0);
return ans;
}
