#include "werewolf.h"
#include <bits/stdc++.h>
using namespace std;
const int maxN = 400000;
typedef pair<int,int> ii;
struct UFDS{
int p[maxN];
void reset(int n){
for(int i = 0;i < n;i++) p[i] = i;
}
int findSet(int u){
if(p[u] == u) return u;
else{
p[u] = findSet(p[u]);
return p[u]; ///use path compression only
}
}
void unionSet(int u, int v){
u = findSet(u);
v = findSet(v);
if(u == v) return;
if(u > v) swap(u,v);
p[u] = v; ///don't union by rank, instead return the largest value to make tree building easier
}
};
struct query{
int start;
int end;
int L;
int R;
int id;
int humanSubtree; ///idx of subtree
int humanLow; ///preorder left endpoint
int humanHigh; ///preorder right endpoint
int wolfSubtree; ///idx of subtree
int wolfLow; ///preorder left endpoint
int wolfHigh; ///preorder right endpoint
};
struct edge{
int u;
int v;
int w;
};
struct tree{
vector<int> child[maxN];
int low[maxN];
int high[maxN];
int cnt = 0;
void addEdge(int parent, int c){
child[parent].push_back(c);
}
///basically like a preorder, but don't label the non-leaves
void dfs(int u){
low[u] = 102345678;
high[u] = -1;
if(child[u].empty()){
low[u] = cnt;
high[u] = cnt;
cnt++;
return;
}
for(int v : child[u]){
dfs(v);
low[u] = min(low[u],low[v]);
high[u] = max(high[u],high[v]);
}
}
};
struct segment{
int seg[maxN]; int n;
void create(int nn){
n = nn;
for(int i = 0;i < 2*n;i++) seg[i] = -1e8;
}
void update(int i, int v){
i += n;
while(i > 0){
seg[i] = max(seg[i],v);
i >>= 1;
}
}
int Query(int l, int r){
int ans = -1e8;
for(l += n, r += n;l < r;l >>= 1, r >>= 1){
if(l&1){
ans = max(ans, seg[l]);
l++;
}
if(r&1){
r--;
ans = max(ans, seg[r]);
}
}
return ans;
}
};
bool edgeComp(edge a, edge b){
return a.w < b.w;
}
bool queryCompHuman(query a, query b){
return a.L > b.L;
}
bool queryCompWolf(query a, query b){
return a.R < b.R;
}
bool queryHighComp(query a, query b){
return a.humanHigh < b.humanHigh;
}
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 m = X.size();
int q = S.size();
vector<int> answer;
answer.assign(q,0);
query queries[q+1];
for(int i = 0;i < q;i++){
queries[i] = {S[i],E[i],L[i],R[i],i,-1,-1,-1,-1};
}
edge edges[m];
UFDS uf;
tree human; tree wolf;
///Building the tree for the start/human form
///In the new tree, if a node has a value X, all leaves in that subtree will be reachable if L = X, (i.e. all leaves nodes have value >= X)
for(int i = 0;i < m;i++) edges[i] = {X[i],Y[i],min(X[i],Y[i])};
sort(edges,edges+m,edgeComp);
reverse(edges,edges+m); ///decreasing weight
sort(queries,queries+q,queryCompHuman); ///decreasing L
queries[q].L = -1; ///dummy element to ensure entire tree is comepleted
uf.reset(2*n);
int newNode = n;
int edgePtr = 0;
for(int i = 0;i <= q;i++){
while(edgePtr < m && edges[edgePtr].w >= queries[i].L){
int u = uf.findSet(edges[edgePtr].u);
int v = uf.findSet(edges[edgePtr].v);
edgePtr++;
if(u == v) continue;
///connect the two greatest parents to another parent
uf.unionSet(u,newNode);
uf.unionSet(v,newNode);
human.addEdge(newNode,u);
human.addEdge(newNode,v);
newNode++;
}
///the representitive subtree is the subtree of the greatest parent at the current moment
if(i != q) queries[i].humanSubtree = uf.findSet(queries[i].start);
}
///Building the tree for the end/wolf form
///In the new tree, if a node has a value X, all leaves in that subtree will be reachable if R = X, (i.e. all leaves nodes have value <= X)
for(int i = 0;i < m;i++) edges[i] = {X[i],Y[i],max(X[i],Y[i])};
sort(edges,edges+m,edgeComp); ///increasing weight
sort(queries,queries+q,queryCompWolf); ///increasing R
queries[q].R = 1e7; ///dummy element to ensure entire tree is comepleted
uf.reset(2*n);
newNode = n;
edgePtr = 0;
for(int i = 0;i <= q;i++){
while(edgePtr < m && edges[edgePtr].w <= queries[i].R){
int u = uf.findSet(edges[edgePtr].u);
int v = uf.findSet(edges[edgePtr].v);
edgePtr++;
if(u == v) continue;
///connect the two greatest parents to another parent
uf.unionSet(u,newNode);
uf.unionSet(v,newNode);
wolf.addEdge(newNode,u);
wolf.addEdge(newNode,v);
newNode++;
}
///the representitive subtree is the subtree of the greatest parent at the current moment
if(i != q) queries[i].wolfSubtree = uf.findSet(queries[i].end);
}
///Now, we run a preorder on the tree, but don't label to edges. This way, we can convert each query into checking whether two sets of elements have any element in common
human.dfs(2 * n - 2);
wolf.dfs(2 * n - 2);
//for(int i = 0;i < 2*n-1;i++){
// cout << human.low[i] << " " << human.high[i] << " " << wolf.low[i] << " " << wolf.high[i] << "\n";
//}
///Low and High represent the ranges, we need to check if the human range and the wolf range intersect
///Note: intersect here means the following:
///In each of the human tree, each node on the original graph corresponds to another number on the human tree
///Same for the wolf tree
///Each query is a consecutive range of numbers of both trees.
///If we convert each of the numbers in the ranges of the trees back to the original index, we query whether there exist a vertex that is shared on both graphs
for(int i = 0;i < q;i++){
queries[i].humanLow = human.low[queries[i].humanSubtree];
queries[i].humanHigh = human.high[queries[i].humanSubtree];
queries[i].wolfLow = wolf.low[queries[i].wolfSubtree];
queries[i].wolfHigh = wolf.high[queries[i].wolfSubtree];
//cout << queries[i].id << " " << queries[i].humanSubtree << " " << queries[i].wolfSubtree << " " << queries[i].humanLow << " " << queries[i].humanHigh << " " << queries[i].wolfLow << " " << queries[i].wolfHigh << "\n";
}
///Use a segment tree to answer this type of queries
segment seg;
seg.create(n);
///convert stores which number of the human tree corresponds to which number on the wolf tree
ii convert[n];
for(int i = 0;i < n;i++) convert[i] = ii(human.low[i],wolf.low[i]);
sort(convert,convert + n);
sort(queries,queries+q,queryHighComp);
int ptr = 0;
for(int i = 0;i < q;i++){
query qu = queries[i];
while(ptr < n && qu.humanHigh >= convert[ptr].first){
seg.update(convert[ptr].second, convert[ptr].first);
//cout << convert[ptr].second << " " << convert[ptr].first << "\n";
ptr++;
}
//cout << qu.id << " " << seg.Query(qu.wolfLow, qu.wolfHigh + 1) << "\n";
if(seg.Query(qu.wolfLow, qu.wolfHigh + 1) >= qu.humanLow){
answer[qu.id] = 1;
}
else{
answer[qu.id] = 0;
}
}
return answer;
}
