// 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 Query
{
int s, e, l, r, id;
};
int cid, id, pos[N], ptr[N], n, m, q, mx[N], mn[N], querymx[N], querymn[N], parent[N], sz[N];
vector<int> ans;
pair<int, int> child[N];
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)
{
// cout << c << " ";
if (child[c].first == -1)
{
pos[c] = id;
ptr[id] = c;
id++;
return;
}
dfs(child[c].first);
// cout << c << " ";
dfs(child[c].second);
// cout << c << " ";
}
inline 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.r < b.r;
}
inline bool cmp2(Query a, Query b)
{
return a.l > b.l;
}
inline 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);
cid = n;
id = 0;
vector<int> adj[n + 1];
vector<Query> query;
for (int x = 0; x < m; x++)
{
adj[a[x]].push_back(b[x]);
adj[b[x]].push_back(a[x]);
}
reset(2 * n);
for (int x = 0; x < n; x++)
{
child[x] = {-1, -1};
for (int i : adj[x])
{
if (i < x)
{
update1(i, x);
}
}
}
// cout << cid << "\n";
dfs(cid - 1);
reset(2 * n);
// for (int x = 0; x < n; x++)
// {
// cout << pos[x] << " ";
// }
// cout << "\n";
for (int x = 0; x < q; x++)
{
query.push_back({s[x], e[x], l[x], r[x], x});
}
sort(query.begin(), query.end(), cmp1);
int id = 0;
for (int x = 0; x < n; x++)
{
int p = pos[x];
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]);
querymx[query[id].id] = mx[p];
querymn[query[id].id] = mn[p];
id++;
}
else
{
break;
}
}
}
reset(2 * n);
sort(query.begin(), query.end(), cmp2);
id = 0;
for (int x = n - 1; x >= 0; x--)
{
int p = pos[x];
for (int i : adj[x])
{
if (i > x)
{
int j = pos[i];
// cout << j << " " << i << "\n";
update2(p, j);
}
}
while (id < q)
{
if (query[id].l == x)
{
int p = getParent(pos[query[id].s]);
int i = query[id].id;
// cout << mn[p] << " " << mx[p] << "\n";
if(min(querymx[i], mx[p]) >= max(querymn[i], mn[p]))
{
ans[i] = 1;
}
else
{
ans[i] = 0;
}
id++;
}
else
{
break;
}
}
}
return ans;
}
