#include "werewolf.h"
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
const int N = 200200;
struct PersistentFenwick {
vector<pair<int, ll>> fw[N]; // value, version
int n;
void init(int _n) {
n = _n;
for (int i = 1;i <= n;i++) fw[i].push_back({ 0, 0ll });
}
void update(int v, ll w, int ver) {
for (int i = v;i <= n;i += i & -i) {
fw[i].push_back({ ver, fw[i].back().second + w });
}
}
ll query(int ver, int v) {
ll ans = 0;
for (int i = v;i > 0;i -= i & -i) {
ans += (--upper_bound(fw[i].begin(), fw[i].end()
, pair<int, ll>(ver, LLONG_MAX)))->second;
}
return ans;
}
} fw;
struct Query {
int r, s, e, idx;
};
vector<Query> Q[N];
int n, p[N];
int fr(int i) {
return p[i] == i ? i : p[i] = fr(p[i]);
}
vector<int> adj_mn[N], adj_mx[N];
vector<int> adj1[N], adj2[N];
int tot;
int val1[N], val2[N], jump1[19][N], jump2[19][N];
int in1[N], out1[N], in2[N], out2[N], re[N];
void dfs1(int v, int p) {
jump1[0][v] = p;
in1[v] = ++tot;
re[tot] = v;
for (auto& x : adj1[v]) {
dfs1(x, v);
}
out1[v] = tot;
}
void dfs2(int v, int p) {
jump2[0][v] = p;
in2[v] = ++tot;
for (auto& x : adj2[v]) {
dfs2(x, v);
}
out2[v] = tot;
}
vector<int> check_validity(int NN, vector<int> X, vector<int> Y, vector<int> S, vector<int> E,
vector<int> L, vector<int> R) {
n = NN;
for (int i = 0;i < n;i++) p[i] = i;
int m = X.size();
for (int i = 0;i < m;i++) {
int u = X[i], v = Y[i];
if (u > v) swap(u, v);
adj_mn[u].push_back(v);
adj_mx[v].push_back(u);
}
// Build KRT from >= L (from suffix)
{
for (int i = 0;i < n;i++) p[i] = i;
for (int i = n - 1;i >= 0;i--) {
for (auto& x : adj_mn[i]) {
int pv = fr(x);
if (i == pv) continue;
adj1[i].push_back(pv);
p[pv] = i;
}
}
tot = 0;
dfs1(0, 0);
}
// Build KRT from <= R (from prefix)
{
for (int i = 0;i < n;i++) p[i] = i;
for (int i = 0;i < n;i++) {
for (auto& x : adj_mx[i]) {
int pv = fr(x);
if (i == pv) continue;
adj2[i].push_back(pv);
p[pv] = i;
}
}
tot = 0;
dfs2(n - 1, n - 1);
}
for (int i = 1;i < 19;i++) {
for (int j = 0;j < n;j++) {
jump1[i][j] = jump1[i - 1][jump1[i - 1][j]];
jump2[i][j] = jump2[i - 1][jump2[i - 1][j]];
}
}
fw.init(n);
for (int i = 1;i <= n;i++) {
fw.update(in2[re[i]], 1, i);
}
int q = S.size();
vector<int> ans(q);
for (int i = 0;i < q;i++) {
int now = S[i];
int now2 = E[i];
for (int j = 18;j >= 0;j--) {
if (jump1[j][now] >= L[i]) {
now = jump1[j][now];
}
if (jump2[j][now2] <= R[i]) {
now2 = jump2[j][now2];
}
}
int res = 0;
res += fw.query(out1[now], out2[now2]) - fw.query(in1[now] - 1, out2[now2]);
res -= fw.query(out1[now], in2[now2] - 1) - fw.query(in1[now] - 1, in2[now2] - 1);
ans[i] = (res > 0);
}
return ans;
}
/*
6 6 3
5 1
1 2
1 3
3 4
3 0
5 2
4 2 1 2
4 2 2 2
5 4 3 4
*/
