#include <bits/stdc++.h>
#define pb push_back
#include "werewolf.h"
using namespace std;
const int maxn = 4e5 + 10;
int n, m, q;
vector < int > g[maxn];
struct query
{
int l, r, s, e;
query(){};
query(int _l, int _r, int _s, int _e)
{
l = _l;
r = _r;
s = _s;
e = _e;
}
};
/// seg
int t[maxn * 4];
int ql, qr;
int doquery(int i, int l, int r)
{
if(qr < l || ql > r)return 0;
if(ql <= l && r <= qr)return t[i];
int mid = (l + r)/2;
return doquery(2*i, l, mid) + doquery(2*i+1, mid+1, r);
}
int make_query(int queryl, int queryr)
{
ql = queryl;
qr = queryr;
return doquery(1, 1, n);
}
int updpos, updval;
void update(int i, int l, int r)
{
if(l == r)
{
t[i] = updval;
return;
}
int mid = (l + r)/2;
if(updpos <= mid)update(2*i, l, mid);
else update(2*i+1, mid+1, r);
t[i] = t[2*i] + t[2*i+1];
}
void make_update(int pos, int val)
{
updpos = pos;
updval = val;
update(1, 1, n);
}
query ask[maxn];
vector < int > emax, emin;
struct dsu_tree /// mintree -> pref, ends in n-1
{ /// maxtree -> suff, ends in 0
int tmr, sz;
vector < int > t;
vector < int > p;
vector < int > tin, tout;
vector < vector < int > > adj;
vector < int > pos;
vector < vector < int > > jump;
vector < int > val;
dsu_tree(int n)
{
tmr = 0;
p.resize(2*n); /// dsu
/// in reconstruction tree
t.resize(2*n);
adj.resize(2*n);
val.resize(2*n);
/// later on
tin.resize(2*n);
tout.resize(2*n);
jump.resize(2*n);
pos.resize(2*n);
for (int i = 0; i < n; ++ i)
{
p[i] = i;
t[i] = i;
sz ++;
}
}
/// dsu stuff
int find_leader(int i)
{
if(p[i] == i)return i;
return (find_leader(p[i]));
}
void add_edge(int v, int u, int w)
{
// cout << "adding edge " << v << " " << u << " with " << w << endl;
int leadv = find_leader(v);
int leadu = find_leader(u);
if(leadv == leadu)return;
p[leadu] = leadv;
/// v novoto dyrvo
u = t[leadu];
v = t[leadv];
t[leadv] = sz;
adj[sz].pb(v);
adj[sz].pb(u);
val[sz] = w;
sz ++;
}
/// euler stuff
void euler(int beg, int from, bool type)
{
if(type == 0)
emin.pb(beg);
else emax.pb(beg);
jump[beg].resize(20);
jump[beg][0] = from;
for (int j = 1; j < 20; ++ j)
{
if(jump[beg][j-1] == -1)
{
jump[beg][j] = -1;
continue;
}
jump[beg][j] = jump[jump[beg][j-1]][j-1];
}
if(adj[beg].size() == 0)
{
tmr ++;
tin[beg] = tmr-1;
tout[beg] = tmr-1;
pos[beg] = tmr-1;
return;
}
tin[beg] = 1e9;
tout[beg] = -1;
for (auto nb: adj[beg])
{
if(nb == from)continue;
euler(nb, beg, type);
tin[beg] = min(tin[beg], tin[nb]);
tout[beg] = max(tout[beg], tout[nb]);
}
}
};
struct segm
{
int lmax, rmax, lmin, rmin;
segm(){};
segm(int _lmax, int _rmax, int _lmin, int _rmin)
{
lmax = _lmax;
rmax = _rmax;
lmin = _lmin;
rmin = _rmin;
}
};
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;
m = L.size();
q = S.size();
for (int i = 0; i < X.size(); ++ i)
{
int from = X[i], to = Y[i];
g[from].pb(to);
g[to].pb(from);
}
for (int i = 0; i < m; ++ i)
{
ask[i] = query(L[i], R[i], S[i], E[i]);
}
dsu_tree mintree(n), maxtree(n);
for (int i = 0; i < n; ++ i)
{
for (auto j: g[i])
{
if(j >= i)continue;
mintree.add_edge(i, j, i);
}
}
int szmin = mintree.sz;
mintree.euler(szmin-1, -1, 0);
for (int i = n-1; i >= 0; -- i)
{
for (auto j: g[i])
{
if(j <= i)continue;
maxtree.add_edge(mintree.pos[i], mintree.pos[j], i);
}
}
// int szmin = mintree.sz;
int szmax = maxtree.sz;
// mintree.euler(szmin-1, -1, 0);
maxtree.euler(szmax-1, -1, 1);
/* for (int i = 0; i < 2*n; ++ i)
cout << mintree.tin[i] << " " << mintree.tout[i] << endl;
cout << endl;
for (int i = 0; i < 2*n; ++ i)
cout << maxtree.tin[i] << " " << maxtree.tout[i] << endl;
cout << endl;*/
std::vector < int > ans;
vector < segm > sg;
ans.resize(q, 0);
vector < vector < int > > st, fi;
st.resize(2*n+1);
fi.resize(2*n+1);
for (int i = 0; i < q; ++ i)
{
int from = mintree.pos[ask[i].s];
int to = ask[i].e;
//cout << "* " << from << " " << to << endl;
for (int bit = 19; bit >= 0; -- bit)
{
if(maxtree.jump[from][bit] != -1 && maxtree.val[maxtree.jump[from][bit]] >= ask[i].l)
from = maxtree.jump[from][bit];
}
for (int bit = 19; bit >= 0; -- bit)
{
if(mintree.jump[to][bit] != -1 && mintree.val[mintree.jump[to][bit]] <= ask[i].r)
to = mintree.jump[to][bit];
}
// cout << from << " " << to << endl;
// cout << maxtree.tin[from ] << " " << maxtree.tout[from ] << endl;
//cout << maxtree.tin[from ] << " " << maxtree.tout[from] << " " << mintree.tin[to] << " " << max
sg.pb(segm(maxtree.tin[from], maxtree.tout[from], mintree.tin[to], mintree.tout[to]));
}
for (int i = 0; i < sg.size(); ++ i)
{
// cout << sg[i].lmax << " " << sg[i].rmax << " " << sg[i].lmin << " " << sg[i].rmin << endl;
int lt = sg[i].lmax, rt = sg[i].rmax;
if(lt)fi[lt - 1].pb(i);
st[rt].pb(i);
}
for (int i = 0; i < n; ++ i)
{
make_update(mintree.pos[i], 1);
for (auto &x: fi[i])
{
long long num = make_query(sg[x].lmax, sg[x].rmax);
ans[x] -= num;
}
for (auto &x: st[i])ans[x] += make_query(sg[x].lmax, sg[x].rmax);
}
for (int i = 0; i <ans.size(); ++ i)
{
if(ans[i] > 0)ans[i] = 1;
}
return ans;
}
