#include "werewolf.h"
#include <bits/stdc++.h>
using namespace std;
#define f first
#define s second
#pragma "std=c++20"
struct Query {
int iQ, from, to, humanLB, wolfUB;
};
struct SumQ {
int human, wolfL, wolfR, iq, sign;
};
bool cmpSumQ (const SumQ& a, const SumQ& b) {
return tie(a.human, a.wolfL, a.wolfR) < tie(b.human, b.wolfL, b.wolfR);
}
int numV, numE, numQ;
vector<Query> queries;
vector<pair<int,int>> edges;
vector<int> ans;
struct DSU {
int N;
vector<int> par;
DSU (int n) {
N = n;
par.resize(N);
iota(par.begin(), par.end(), 0);
}
int find (int x) {
if (par[x] == x) return x;
else return par[x] = find(par[x]);
}
bool combine (int x, int y) {
x = find(x), y = find(y);
if (x == y) return false;
par[y] = x;
return true;
}
bool sameCC (int x, int y) {
x = find(x), y = find(y);
return (x == y);
}
};
struct Segtree {
int numleaves;
vector<int> sum;
Segtree (int n) {
numleaves = 1;
while (numleaves < n) numleaves *= 2;
sum.assign(2*numleaves, 0);
}
int query (int l, int r) {
l += numleaves, r += numleaves+1;
int res = 0;
while (l < r) {
if (l&1) {
res += sum[l++];
}
if (r&1) {
res += sum[--r];
}
l /= 2;
r /= 2;
}
return res;
}
void update (int idx, int val) {
idx += numleaves;
sum[idx] += val;
idx /= 2;
while (idx > 0) {
sum[idx] = sum[2*idx] + sum[2*idx+1];
idx /= 2;
}
}
};
template<auto cmp, bool side>
struct Tree {
vector<vector<int>> tree;
vector<int> cmpST;
vector<int> tIn, tOut;
vector<vector<int>> jump;
int t;
bool cmpSide (int a, int b) {
if (side) return a < b;
else return a > b;
}
void dfs (int node, int par) {
tIn[node] = t++;
for (int child : tree[node]) {
if (child != par) {
jump[child][0] = node;
dfs(child, node);
}
}
tOut[node] = t-1;
}
int jumpQ (int node, int valQ) {
for (int len = 31; len >= 0; len--) {
if (cmpSide(cmpST[jump[node][len]], valQ) || valQ == cmpST[jump[node][len]]) {
node = jump[node][len];
}
}
return node;
}
Tree () {
tree.resize(2*numV), tIn.resize(2*numV), tOut.resize(2*numV), cmpST.resize(2*numV);
jump.resize(2*numV, vector<int>(32));
vector<pair<int,int>> edgeList(numE);
copy(edges.begin(), edges.end(), edgeList.begin());
sort(edgeList.begin(), edgeList.end(), [&](const pair<int,int>& a, const pair<int,int>& b) {
return cmpSide((*cmp)(a.f, a.s), (*cmp)(b.f, b.s));
});
iota(cmpST.begin(), cmpST.end(), 0);
DSU dsu(2*numV);
int nodeOn = numV;
for (int iEdge = 0; iEdge < numE; iEdge++) {
pair<int,int> edgeOn = edgeList[iEdge];
if (!dsu.sameCC(edgeOn.f, edgeOn.s)) {
tree[nodeOn].push_back(dsu.find(edgeOn.f));
tree[nodeOn].push_back(dsu.find(edgeOn.s));
cmpST[nodeOn] = (*cmp)(cmpST[dsu.find(edgeOn.f)], cmpST[dsu.find(edgeOn.s)]);
dsu.combine(edgeOn.f, edgeOn.s);
dsu.combine(nodeOn, edgeOn.f);
nodeOn++;
}
}
t = 0;
for (int i = 0; i < 2*numV; i++) {
for (int len = 0; len < 32; len++) {
jump[i][len] = nodeOn-1;
}
}
dfs(nodeOn-1, -1);
// for (int i = 0; i < 2*numV; i++) cerr << tIn[i] << " " << tOut[i] << "\n";
for (int len = 1; len < 32; len++) {
for (int i = 0; i < numV; i++) {
jump[i][len] = jump[jump[i][len-1]][len-1];
}
}
}
};
int mini (int a, int b) {return min(a, b);}
int maxi (int a, int b) {return max(a, b);}
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) {
numQ = (int)S.size();
numV = N;
numE = (int)X.size();
queries.resize(numQ);
for (int iq = 0; iq < numQ; iq++) {
queries[iq] = Query{iq, S[iq], E[iq], L[iq], R[iq]};
}
edges.resize(numE);
for (int i = 0; i < numE; i++) {
edges[i] = make_pair(X[i], Y[i]);
}
Tree<mini, false> humanTree;
// cerr << "\n";
Tree<maxi, true> wolfTree;
// cerr << "\n";
vector<pair<int,int>> points(2*numV);
for (int i = 0; i < numV; i++) {
points.push_back(make_pair(humanTree.tIn[i], wolfTree.tIn[i]));
}
sort(points.begin(), points.end());
vector<SumQ> updates;
for (int iq = 0; iq < numQ; iq++) {
Query queryOn = queries[iq];
int humanL = humanTree.tIn[humanTree.jumpQ(queryOn.from, queryOn.humanLB)];
int humanR = humanTree.tOut[humanTree.jumpQ(queryOn.from, queryOn.humanLB)];
int wolfL = wolfTree.tIn[wolfTree.jumpQ(queryOn.to, queryOn.wolfUB)];
int wolfR = wolfTree.tOut[wolfTree.jumpQ(queryOn.to, queryOn.wolfUB)];
updates.push_back(SumQ{humanL-1, wolfL, wolfR, iq, -1});
updates.push_back(SumQ{humanR, wolfL, wolfR, iq, 1});
}
sort(updates.begin(), updates.end(), cmpSumQ);
ans.resize(numQ);
int iPoint = 0, iUpdate = 0;
Segtree segQ(2*numV+1);
for (int iHuman = -1; iHuman < 2*numV; iHuman++) {
while (iPoint < (int)points.size() && points[iPoint].f == iHuman) {
pair<int,int> pointOn = points[iPoint];
segQ.update(pointOn.s, 1);
iPoint++;
}
while (iUpdate < (int)updates.size() && updates[iUpdate].human == iHuman) {
SumQ queryOn = updates[iUpdate];
ans[queryOn.iq] += queryOn.sign * segQ.query(queryOn.wolfL, queryOn.wolfR);
iUpdate++;
}
}
for (int& val : ans) {
if (val > 0) {
val = 1;
}
else {
val = 0;
}
}
return ans;
}
