#include "werewolf.h"
#include<bits/stdc++.h>
#define f0r(i,n) for(int i = 0; i<n; i++)
#define pb push_back
#define vi vector<int>
using namespace std;
const int mxn = 200005;
int tree[mxn*4][2];
int n;
bool intersect(pair<int,int>a, pair<int,int>b){
if(a.first > b.first)swap(a,b);
if(a.first > a.second || b.first > b.second)return false;
if(a.second < b.first)return false;
else return true;
}
int quer(int l, int r, int d){
l += n;
r+=n;
int s = 0;
while(l<=r){
if(l % 2 == 1)s += tree[l++][d];
if(r % 2 == 0)s += tree[r--][d];
l/=2;
r/=2;
}
return s;
}
void upd(int k, int x, int d){
k += n;
tree[k][d] = x;
for(k/=2; k>=1; k/=2){
tree[k][d] = tree[k*2][d] + tree[k*2+1][d];
}
}
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;
int Q = S.size();
int m = X.size();
vector<int>adj[N];
f0r(i, m){
adj[X[i]].pb(Y[i]);
adj[Y[i]].pb(X[i]);
}
vector<int>ans(Q);
//N <= 3000 && m <= 6000 && Q <= 3000
if(false){
f0r(t, Q){
int s = S[t];
int e = E[t];
int l = L[t];
int r = R[t];
vector<bool>vis(N, 0);
vector<bool>wis(N, 0);
queue<int>q;
if(s >= l){
vis[s] = 1;
q.push(s);
}
while(!q.empty()){
int node = q.front();
q.pop();
for(auto u : adj[node]){
if(vis[u])continue;
if(u < l)continue;
vis[u] = 1;
q.push(u);
}
}
if(e <= r){
wis[e] = 1;
q.push(e);
}
while(!q.empty()){
int node = q.front();
q.pop();
for(auto u : adj[node]){
if(wis[u])continue;
if(u > r)continue;
wis[u] = 1;
q.push(u);
}
}
int a = 0;
f0r(i,N){
if(vis[i] && wis[i])a = 1;
}
ans[t] = a;
}
return ans;
}
else{
int fi;
f0r(i,N){
if(adj[i].size() == 1)fi = i;
}
vi dex;
dex.pb(fi);
vector<bool>vis(N, 0);
vis[fi] = 1;
queue<int>q;
q.push(fi);
while(!q.empty()){
int node = q.front();
q.pop();
for(auto u : adj[node]){
if(vis[u])continue;
vis[u] = 1;
dex.pb(u);
q.push(u);
}
}
vi invmap(N);
f0r(i, N){
invmap[dex[i]] = i;
}
vector<vi>lefts;
vector<vi>rights;
f0r(i, Q){
lefts.pb({L[i], invmap[S[i]], i});
rights.pb({R[i], invmap[E[i]], i});
}
sort(lefts.begin(), lefts.end());
sort(rights.rbegin(), rights.rend());
//for(auto u : invmap)cout<<u<<' ';
//cout<<'\n';
f0r(i, n){
upd(i, 1, 0);
upd(i, 1, 1);
}
int cur = -1;
vector<pair<int,pair<int,int>>>la;
vector<pair<int,pair<int,int>>>ra;
f0r(i,Q){
if(lefts[i][0]-1 > cur){
for(int j = cur + 1; j <= lefts[i][0]-1; j++){
upd(invmap[j], 0, 0);
}
cur = lefts[i][0]-1;
}
f0r(j, n){
//cout<<tree[j+n][0]<<' ';
}
//cout<<'\n';
//f0r(j,3)cout<<lefts[i][j]<<' ';
//cout<<'\n';
//bs the first index in [l, N] to have a 0
int l = lefts[i][1];
int lo = l;
int hi = N;
//cout<<lo<<' '<<hi<<'\n';
while(lo < hi){
//cout<<lo<<' '<<hi<<'\n';
int mid = lo + (hi - lo)/2;
if(quer(l, mid, 0) < mid - l + 1){
hi = mid;
}
else{
lo = mid + 1;
}
}
int lo2 = -1;
int hi2 = l;
while(lo2 < hi2){
int mid = lo2 + (hi2 - lo2 + 1)/2;
if(quer(mid, l, 0) < l - mid + 1){
lo2 = mid;
}
else{
hi2 = mid - 1;
}
}
la.pb({lefts[i][2], {lo2+1, lo-1}});
}
cur = N;
f0r(i,Q){
if(rights[i][0]+1 < cur){
for(int j = cur - 1; j >= rights[i][0]+1; j--){
upd(invmap[j], 0, 1);
}
cur = rights[i][0]+1;
}
//bs the last index in [-1, r] to have a 0
int r = rights[i][1];
int lo = -1;
int hi = r;
while(lo < hi){
int mid = lo + (hi - lo + 1)/2;
if(quer(mid, r, 1) < r - mid + 1){
lo = mid;
}
else{
hi = mid - 1;
}
}
int lo2 = r;
int hi2 = n;
while(lo2 < hi2){
int mid = lo2 + (hi2 - lo2)/2;
if(quer(r, mid, 1) < mid - r + 1){
hi2 = mid;
}
else{
lo2 = mid + 1;
}
}
ra.pb({rights[i][2], {lo+1, lo2-1}});
}
sort(la.begin(), la.end());
sort(ra.begin(), ra.end());
//for(auto u : la)cout<<u.second.first<<' '<<u.second.second<<' ';
//cout<<'\n';
//for(auto u : ra)cout<<u.second.first<<' '<<u.second.second<<' ';
//cout<<'\n';
vi ans(Q);
f0r(i, Q){
if(intersect(la[i].second, ra[i].second))ans[i] = 1;
else ans[i] = 0;
}
return ans;
//return {};
}
}
