// Starcraft 2 enjoyer //
#include <bits/stdc++.h>
#include "werewolf.h"
// #pragma GCC target("avx2")
// #pragma GCC optimize("O3")
// #pragma GCC optimize("unroll-loops")
using namespace std;
#define LSOne(X) ((X) & -(X))
const int N = 4e5 + 5;
const int K = 1e2 + 5;
const int LG = 20;
const int INF = 1e9 + 5;
const int B = 1000;
const int MOD = 1e9 + 7;
struct Fenwick
{
vector<int> ft;
int n;
Fenwick(int len)
{
n = len;
ft.assign(n + 1, 0);
}
void update(int pos, int val)
{
while (pos <= n)
{
ft[pos] += val;
pos += LSOne(pos);
}
}
int get(int pos)
{
int sum = 0;
while (pos > 0)
{
sum += ft[pos];
pos -= LSOne(pos);
}
return sum;
}
int get(int l, int r)
{
return get(r) - get(l - 1);
}
};
struct Query
{
int s, e, l, r, id;
};
struct Query2
{
int y, x, z, t, id;
};
int cid, id, pos[N], n, m, q, mx[N], mn[N], parent[N], sz[N], lx[N], rx[N], ly[N], ry[N], px[N], py[N];
vector<int> ans, adj[N];
pair<int, int> child[N];
vector<Query> query;
inline int getParent(int x)
{
return parent[x] == x ? x : parent[x] = getParent(parent[x]);
}
inline void update1(int a, int b)
{
a = getParent(a);
b = getParent(b);
if (a != b)
{
child[cid] = {a, b};
parent[b] = cid;
parent[a] = cid;
cid++;
}
}
inline void update2(int a, int b)
{
a = getParent(a);
b = getParent(b);
if (a != b)
{
if (sz[a] < sz[b])
{
swap(a, b);
}
parent[b] = a;
sz[a] += sz[b];
mx[a] = max(mx[a], mx[b]);
mn[a] = min(mn[a], mn[b]);
}
}
inline void dfs(int c)
{
if (child[c].first == -1)
{
pos[c] = id;
id++;
return;
}
dfs(child[c].first);
dfs(child[c].second);
}
void reset(int n)
{
for (int x = 0; x <= n; x++)
{
parent[x] = x;
sz[x] = 1;
mx[x] = x;
mn[x] = x;
child[x].first = child[x].second = -1;
}
}
inline bool cmp1(Query a, Query b)
{
return a.l > b.l;
}
inline bool cmp2(Query a, Query b)
{
return a.r < b.r;
}
inline bool cmp3(Query2 a, Query2 b)
{
if (a.y != b.y)
return a.y < b.y;
if (a.z == -1 && b.z == -1)
return a.y < b.y;
if (a.z == -1)
return 1;
if (b.z == -1)
return 0;
return a.x < b.x;
}
inline void cal1()
{
cid = n;
id = 0;
sort(query.begin(), query.end(), cmp1);
reset(2 * n);
for (int x = n - 1; x >= 0; x--)
{
for (int i : adj[x])
{
if (x < i)
{
update1(i, x);
}
}
}
dfs(cid - 1);
reset(2 * n);
int id = 0;
for (int x = n - 1; x >= 0; x--)
{
int p = pos[x];
px[x] = p;
for (int i : adj[x])
{
if (i > x)
{
int j = pos[i];
update2(p, j);
// cout << p << " " << j << "ed\n";
}
}
while (id < q)
{
if (query[id].l == x)
{
int p = getParent(pos[query[id].s]);
int i = query[id].id;
lx[i] = mn[p];
rx[i] = mx[p];
// cout << lx[i] << " " << rx[i] << "w\n";
id++;
}
else
{
break;
}
}
}
}
inline void cal2()
{
cid = n;
id = 0;
sort(query.begin(), query.end(), cmp2);
reset(2 * n);
for (int x = 0; x < n; x++)
{
for (int i : adj[x])
{
if (i < x)
{
update1(i, x);
}
}
}
dfs(cid - 1);
reset(2 * n);
int id = 0;
for (int x = 0; x < n; x++)
{
int p = pos[x];
py[x] = p;
for (int i : adj[x])
{
if (i < x)
{
int j = pos[i];
update2(p, j);
}
}
while (id < q)
{
if (query[id].r == x)
{
int p = getParent(pos[query[id].e]);
int i = query[id].id;
ly[i] = mn[p];
ry[i] = mx[p];
// cout << ly[i] << " " << ry[i] << "v\n";
id++;
}
else
{
break;
}
}
}
}
vector<int> check_validity(int i, vector<int> a, vector<int> b, vector<int> s, vector<int> e, vector<int> l, vector<int> r)
{
n = i;
m = a.size();
q = s.size();
ans.assign(q, 0);
for (int x = 0; x < m; x++)
{
// cout << a[x] << " " << b[x] << "\n";
adj[a[x]].push_back(b[x]);
adj[b[x]].push_back(a[x]);
}
for (int x = 0; x < q; x++)
{
query.push_back({s[x], e[x], l[x], r[x], x});
}
cal1();
cal2();
Fenwick ft(n);
vector<Query2> query2;
for (int x = 0; x < n; x++)
{
query2.push_back({py[x], px[x], -1, -1, -1});
// cout << px[x] << " " << py[x] << "\n";
}
for (int x = 0; x < q; x++)
{
// cout << lx[x] << " " << ly[x] << " " << rx[x] << " " << ry[x] << "\n";
query2.push_back({ly[x] - 1, lx[x], rx[x], -1, x});
query2.push_back({ry[x], lx[x], rx[x], 1, x});
}
sort(query2.begin(), query2.end(), cmp3);
for (Query2 q : query2)
{
if (q.z == -1)
{
// cout << q.x + 1 << "\n";
ft.update(q.x + 1, 1);
}
else
{
// cout << q.x + 1 << " " << q.z + 1 << "\n";
ans[q.id] += 1LL * q.t * ft.get(q.x + 1, q.z + 1);
}
}
for (int x = 0; x < q; x++)
{
if (s[x] < l[x] || e[x] > r[x])
{
ans[x] = 0;
continue;
}
if (ans[x] > 0)
ans[x] = 1;
}
return ans;
}
