#include "werewolf.h"
#include <bits/stdc++.h>
using namespace std;
int n , m , q;
vector<int> u , o , k , l , r;
vector<vector<int>> g;
int t = 0;
int fp(int a){
if(u[a] == -1)return a;
return u[a] = fp(u[a]);
}
void un(int a , int b){
a = fp(a);
b = fp(b);
if(a==b)return;
g[t].push_back(o[a]);
g[t].push_back(o[b]);
o[a] = t;
l[a] = min(l[a] , l[b]);
r[a] = max(r[a] , r[b]);
t++;
u[b] = a;
}
int w = 0;
void dfs(int h){
if(h < n){
k[h] = w;
w++;
}
for(int x : g[h]){
dfs(x);
}
}
vector<int> mf(vector<int> X, vector<int> Y){
u.assign(n , -1);
o.assign(n , -1);
k.assign(n , -1);
l.assign(n , -1);
r.assign(n , -1);
g.assign(2*n , vector<int>());
t = n;
w = 0;
for(int i = 0; i < n; i++){
o[i] = i;
}
vector<vector<int>> g2(n);
for(int i = 0; i < m; i++){
int a = max(X[i] , Y[i]);
int b = min(X[i] , Y[i]);
g2[a].push_back(b);
}
for(int i = 0; i < n; i++){
for(int x : g2[i]){
un(i , x);
}
}
dfs(t-1);
return k;
}
vector<array<int , 2>> mi(vector<int> X, vector<int> Y , vector<int> E , vector<int> R , vector<int> a){
u.assign(n , -1);
o.assign(n , -1);
k.assign(n , -1);
l.assign(n , -1);
r.assign(n , -1);
g.assign(2*n , vector<int>());
t = n;
for(int i = 0; i < n; i++){
o[i] = i;
l[i] = r[i] = a[i];
}
vector<vector<int>> g2(n);
for(int i = 0; i < m; i++){
int a = max(X[i] , Y[i]);
int b = min(X[i] , Y[i]);
g2[a].push_back(b);
}
vector<vector<array<int , 2>>> h1(n);
for(int i = 0; i < q; i++){
h1[R[i]].push_back({E[i] , i});
}
vector<array<int , 2>> ans(q);
for(int i = 0; i < n; i++){
for(int x : g2[i]){
un(i , x);
}
for(int j = 0; j < h1[i].size(); j++){
int b = fp(h1[i][j][0]);
ans[h1[i][j][1]] = {l[b] , r[b]};
}
}
return ans;
}
void fl(vector<int>& X, vector<int>& Y,vector<int>& S, vector<int>& E,vector<int>& L, vector<int>& R){
for(int& x:X)x = n-1-x;
for(int& x:Y)x = n-1-x;
for(int& x:S)x = n-1-x;
for(int& x:E)x = n-1-x;
for(int& x:L)x = n-1-x;
for(int& x:R)x = n-1-x;
}
const int mN = 3*1e5;
int f[mN];
void add(int h , int v){
while(h < mN){
f[h] += v;
h += (-h)&h;
}
}
int get(int h){
int ans = 0;
while(h > 0){
ans += f[h];
h -= (-h)&h;
}
return ans;
}
vector<int> s2(vector<int> a , vector<array<int , 2>> b , vector<int> c , vector<array<int , 2>> d){
vector<int> e(n , -1);
vector<int> ans(q , 0);
for(int i = 0; i < n; i++){
e[c[i]] = a[i];
}
vector<array<int , 4>> h2;
for(int i = 0; i < q; i++){
h2.push_back({d[i][1] , b[i][1] , i , 1});
if(d[i][0] != 0)h2.push_back({d[i][0]-1 , b[i][1] , i , -1});
if(b[i][0] != 0)h2.push_back({d[i][1] , b[i][0]-1 , i , -1});
if(d[i][0] != 0 && b[i][0] != 0)h2.push_back({d[i][0]-1 , b[i][0]-1 , i , 1});
}
sort(h2.begin() , h2.end());
int j = 0;
for(int i = 0; i < n; i++){
add(e[i]+1 , 1);
while(j < h2.size() && h2[j][0] == i){
ans[h2[j][2]]+= h2[j][3]*get(h2[j][1]+1);
j++;
}
}
return ans;
}
vector<int> check_validity(int N, vector<int> X, vector<int> Y,vector<int> S, vector<int> E,vector<int> L, vector<int> R) {
q = S.size();
m = X.size();
n = N;
vector<int> a = mf(X , Y);
vector<array<int , 2>> b = mi(X , Y , E , R , a);
fl(X , Y , S , E , L , R);
vector<int> c = mf(X , Y);
vector<array<int , 2>> d = mi(X , Y , S , L , c);
reverse(c.begin() , c.end());
fl(X , Y , S , E , L , R);
vector<int> ans = s2(a , b , c , d);
for(int& x : ans)x = min(x, 1);
return ans;
}
