#include "werewolf.h"
#include <bits/stdc++.h>
using namespace std;
using pii = pair<int,int>;
using piii = pair<pii, int>;
#define MP make_pair
#define fs first
#define sc second
struct KruskalTree {
int n, id = 0;
vector<int> fa, lid, rid;
vector<vector<int>> anc, e;
KruskalTree(int _n, int rt) : n(_n), fa(vector<int>(_n+3, 0)), lid(fa), rid(fa), anc(vector<vector<int>>(21, vector<int>(n+3, rt))), e( vector<vector<int>>(_n+3) ) {};
int find (int x) {return fa[x] == 0 ? x : fa[x] = find(fa[x]);}
void merge (int x, int y) {
x = find(x), y = find(y);
if (x != y) {
fa[y] = anc[0][y] = x;
e[x].push_back(y);
}
}
void baizheng () {
for (int j = 1; j < 20; j++) for (int i = 1; i <= n; i++) anc[j][i] = anc[j-1][anc[j-1][i]];
}
void dfs (int i) {
lid[i] = ++id;
for (int j : e[i]) dfs(j);
rid[i] = id;
}
};
struct Bit {
int n;
vector<int> a;
Bit (int _n) : a(vector<int>(_n+5,0)), n(_n) {};
void modify (int i, int val) {for (; i <= n; i+= i&-i) a[i] += val;}
int askpre (int i) {
int ret = 0;
for (; i > 0; i -= i&-i) ret += a[i];
return ret;
}
int query (int l, int r) {return askpre(r) - askpre(l-1);}
};
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) {
int Q = S.size();
vector<int> A(Q,0), id(N+3), hehe(N+3);
vector<vector<int>> mye(N+3);
vector<vector<piii>> ins(N+3), del(N+3);
for (int i = 0; i < X.size(); i++) {
mye[X[i]+1].push_back(Y[i]+1);
mye[Y[i]+1].push_back(X[i]+1);
}
KruskalTree StB (N, N), BtS (N, 1); // 以點權為核心的重構樹
for (int i = 1; i <= N; i++) {
for (int j : mye[i]) if (j < i) StB.merge(i, j);
}
for (int i = N; i >= 1; i--) {
for (int j : mye[i]) if (j > i) BtS.merge(i, j);
}
StB.baizheng(); BtS.baizheng();
StB.dfs(N); BtS.dfs(1);
for (int i = 0; i < Q; i++) {
S[i]++, E[i]++, L[i]++, R[i]++;
int rt1 = S[i], rt2 = E[i];
for (int j = 20; j >= 0; j--) if (BtS.anc[j][rt1] >= L[i]) rt1 = BtS.anc[j][rt1];
for (int j = 20; j >= 0; j--) if (StB.anc[j][rt2] <= R[i]) rt2 = StB.anc[j][rt2];
// cout << rt1 << ' ' << rt2 << " " << BtS.lid[rt1] << ' ' << BtS.rid[rt1] << " " << StB.lid[rt2] << ' ' << StB.rid[rt2] << '\n';
if (rt1 < L[i] or rt2 > R[i]) continue;
ins[BtS.lid[rt1]].push_back(MP(MP(StB.lid[rt2], StB.rid[rt2]), i));
del[BtS.rid[rt1]].push_back(MP(MP(StB.lid[rt2], StB.rid[rt2]), i));
}
// for (int i = 1; i <= N; i++) cout << BtS.lid[i] << ' '; cout << '\n';
// for (int i = 1; i <= N; i++) cout << StB.lid[i] << ' '; cout << '\n';
for (int i = 1; i <= N; i++) id[BtS.lid[i]] = StB.lid[i];
Bit bit(N+2);
for (int i = 1; i <= N; i++) {
// cout << id[i] << '\n';
for (auto [p, qid] : ins[i]) A[qid] -= bit.query(p.fs, p.sc);
bit.modify(id[i], 1); // id[i] 為在 Bts 中壓平後的第 i 項在 StB 的 id
for (auto [p,qid] : del[i]) {
A[qid] += bit.query(p.fs, p.sc);
}
}
for (int &x : A) x = (x > 0);
return A;
}
