#include "werewolf.h"
#include <iostream>
#include <cmath>
#include <vector>
#include <utility>
#include <cassert>
using namespace std;
struct unionFind{
vector<int> chef, in, out;
vector<vector<int>> links;
int e = 0;
int find(int x){
if(chef[x] == x)return x;
return chef[x] = find(chef[x]);
}
pair<int,int> getCompoConnexe(int x){
assert(in[x] >0);
assert(out[x]>0);
return make_pair(in[x], out[x]);
}
//l'ordre compte tres fort ici
void make_A_in_B(int a, int b){
a = find(a);
b = find(b);
if(a != b){
links[b].push_back(a);
chef[a] = b;
}
}
void dfs(int node){
in[node] = ++e;
for(int v:links[node])
dfs(v);
out[node] = ++e;
}
void computeEuleurTour(){
e = 0;
for(int i = 0 ; i < chef.size() ; i++){
if(find(i) == i){
dfs(i);
}
}
}
unionFind(int n){
chef.resize(n);
in.resize(n);
out.resize(n);
links.resize(n);
for(int i=0;i<n;i++)chef[i]=i;
}
};
struct req{
int d,f,id;
};
struct Fenwick{
vector<int> vals;
Fenwick(int n){
vals.resize(n+1,0);
}
#define LSONE(x) ((x)&(-x))
void updatePoint(int pos, int v){
while(pos < vals.size()){
vals[pos] += v;
pos += LSONE(pos);
}
}
int get(int i){
int re = 0;
while(i){
re += vals[i];
i -= LSONE(i);
}
return re;
}
int get(int i, int j){
return get(j) - get(i-1);
}
};
vector<int> check_validity(int N, vector<int> X, vector<int> Y,
vector<int> S, vector<int> E,
vector<int> L, vector<int> R) {
//liste d'adjacence
vector<int> links[N];
for(int e = 0 ; e < X.size() ; e++){
links[X[e]].push_back(Y[e]);
links[Y[e]].push_back(X[e]);
}
int Q = S.size();
vector<pair<int,int>> eventH[N], eventW[N];
for(int i = 0 ; i < Q ; i++){
eventH[L[i]].push_back({S[i], i});
eventW[R[i]].push_back({E[i], i});
}
vector<int> queryS(Q), queryE(Q);
unionFind ufW(N), ufH(N);
for(int city = 0 ; city < N ; city++){
for(int u:links[city])if(u < city){
ufW.make_A_in_B(u, city);
}
//on garde en memoire le chef a ce moment city
for(auto event:eventW[city]){
queryE[event.second] = ufW.find(event.first);
}
}
for(int city = N - 1 ; city >= 0 ; city--){
for(int u:links[city])if(u > city){
ufH.make_A_in_B(u, city);
}
//on garde en memoire le chef a ce moment city
for(auto event:eventH[city]){
queryS[event.second] = ufH.find(event.first);
}
}
//conpute les euleurs tours
ufH.computeEuleurTour();
ufW.computeEuleurTour();
const int W = 1 + 2*N;
vector<int> addY[W];//les events pour ajouter les pts dans le fenwick
vector<req> reqs[W];
for(int i = 0 ; i < N ; i++){
addY[ufH.in[i]].push_back(ufW.out[i]);
}
for(int r = 0 ; r < Q ; r++){
auto humanP = ufH.getCompoConnexe(queryS[r]);
auto werewolfP = ufW.getCompoConnexe(queryE[r]);
//pour faire de l'inclusion exclusion
reqs[humanP.first - 1].push_back({werewolfP.first, werewolfP.second, r});
reqs[humanP.second ].push_back({werewolfP.first, werewolfP.second, r});
}
vector<int> ans(Q,-1);
Fenwick ft(W);
for(int x = 0 ; x < W ; x++){
//On met les points sur la D
for(int y:addY[x])ft.updatePoint(y, 1);
for(auto R:reqs[x]){
if(ans[R.id] == -1){//prefix left
ans[R.id] = ft.get(R.d, R.f);
}else{//prefi right
ans[R.id] = ft.get(R.d, R.f) - ans[R.id];
}
}
}
for(int &i:ans)if(i>0)i=1;
return ans;
}
