#include <bits/stdc++.h>
#define pb push_back
#include "werewolf.h"
using namespace std;
const int maxn = 2e5 + 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;
}
};
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;
int pos[maxn];
struct dsu_tree /// mintree -> pref, ends in n-1
{ /// maxtree -> suff, ends in 0
int tmr;
vector < int > p;
vector < int > tin, tout;
vector < vector < int > > adj;
vector < vector < int > > jump;
vector < int > used;
dsu_tree(int n)
{
tmr = 0;
used.resize(n, 0);
p.resize(n);
tin.resize(n);
tout.resize(n);
adj.resize(n);
jump.resize(n);
for (int i = 0; i < n; ++ i)
{
p[i] = i;
}
}
/// dsu stuff
int find_leader(int i)
{
if(p[i] == i)return i;
return (p[i] == find_leader(p[i]));
}
void add_edge(int v, int type)
{
int leadv = find_leader(v);
for (auto u: g[v])
{
if(u > v && type == 0)continue;
if(u < v && type == 1)continue;
if(type == 0)
{
// cout << "add " << u << " " << v << endl;
}
int leadu = find_leader(u);
if(leadv == leadu)continue;
if(type == 0)
{
//cout << v << " " << leadu << endl;
}
p[leadu] = leadv;
adj[v].pb(leadu);
adj[leadu].pb(v);
}
}
/// euler stuff
void euler(int beg, int from, bool type)
{
used[beg] = 1;
//cout << beg << endl;
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-1] = jump[jump[beg][j-1]][j-1];
}
tmr ++;
tin[beg] = tmr;
if(type)
pos[beg] = tmr;
if(type == 0)
emin.pb(beg);
else emax.pb(beg);
for (auto nb: adj[beg])
{
if(used[nb])continue;
euler(nb, beg, type);
}
tout[beg] = tmr;
}
};
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)
mintree.add_edge(i, 0);
for (int i = n-1; i >= 0; -- i)
maxtree.add_edge(i, 1);
mintree.euler(n-1, -1, 0);
maxtree.euler(0, -1, 1);
std::vector < int > ans;
vector < segm > sg;
ans.resize(q, 0);
vector < vector < int > > st, fi;
st.resize(n+1);
fi.resize(n+1);
for (int i = 0; i < m; ++ i)
{
int from = ask[i].s;
int to = ask[i].e;
for (int bit = 19; bit >= 0; -- bit)
{
if(maxtree.jump[from][bit] != -1 && maxtree.jump[from][bit] >= ask[i].l)
from = maxtree.jump[from][bit];
}
for (int bit = 19; bit >= 0; -- bit)
{
if(mintree.jump[from][bit] != -1 && mintree.jump[from][bit] <= ask[i].r)
to = mintree.jump[from][bit];
}
// cout << "real " << from << " " << to << endl;
sg.pb(segm(maxtree.tin[from], maxtree.tout[from], mintree.tin[to], maxtree.tout[to]));
/// from in maxtree, to in mintree
}
for (int i = 0; i < sg.size(); ++ i)
{
int lt = sg[i].lmin, rt = sg[i].rmin;
fi[lt - 1].pb(i);
st[rt].pb(i);
}
for (int i = 1; i <= n; ++ i)
{
make_update(pos[i], 1);
for (auto &x: fi[i])
{
long long num = make_query(sg[x].lmax, sg[x].rmax);
ans[x] -= num; //make_query(segm[x].lmax, segm[x].rmax);
}
for (auto &x: st[i])ans[x] += make_query(sg[x].lmax, sg[x].rmax);
}
return ans;
}
