#include "werewolf.h"
#include <bits/stdc++.h>
#define pb push_back
#define pii pair<int, int>
#define VI vector<int>
#define nyan "(=^･ω･^=)"
#define read_input freopen("in.txt","r", stdin)
#define print_output freopen("out.txt","w", stdout)
typedef long long ll;
typedef long double ld;
using namespace std;
const int maxn = 4e5+10;
int N, M, Q; int tym;
VI adj[2][maxn], sml[maxn], big[maxn];
int parent[2][20][maxn], tour[2][maxn];
int st[2][maxn], ed[2][maxn];
struct disjointSetUnion {
int par[maxn];
void init() { for(int i = 0; i <= N; i++) par[i] = i; }
int find(int x) { return (par[x] == x)? x : par[x] = find(par[x]); }
void join(int a, int b) { par[find(b)] = find(a); }
} dsu;
struct HolyShit {
int ans[maxn];
struct binarytree {
int a[maxn];
int add(int x, int val) {
while(x < maxn) {
a[x] += val;
x += x & -x;
}
}
int sum(int x) {
int ret = 0;
while(x) {
ret += a[x];
x -= x & -x;
} return ret;
}
int range(int l, int r) { return sum(r) - sum(l-1); }
} bit;
struct event {
int x, y1, y2, typ, idx;
event(int _x=0, int _y1 = 0, int _y2=0, int _t=-1, int _i=-1) :
x(_x), y1(_y1), y2(_y2), typ(_t), idx(_i) {}
bool operator<(const event &rhs) {
if(x == rhs.x) return typ < rhs.typ;
return x < rhs.x;
}
}; vector<event> events;
void insert(int x, int y) { x++; y++; events.pb(event(x, y, -1, 1, -1)); }
void query(int x1, int y1, int x2, int y2, int id) {
x1++; y1++; x2++; y2++;
events.pb(event(x1, y1, y2, 0, id));
events.pb(event(x2, y1, y2, 2, id));
}
void process() {
sort(events.begin(), events.end());
//for(auto e : events) {
// cout << e.x << " [" << e.y1 << ", " << e.y2 << "] (" << e.typ << ") " << e.idx <<endl;
//}
for(auto e : events) {
if(e.typ == 0) ans[e.idx] -= bit.range(e.y1, e.y2);
else if(e.typ == 1) bit.add(e.y1, 1);
else ans[e.idx] += bit.range(e.y1, e.y2);
}
}
} ds;
void dfs(int u, int id) {
tour[id][tym] = u;
st[id][u] = tym++;
for(auto v : adj[id][u])
dfs(v, id);
ed[id][u] = tym-1;
}
VI check_validity(int n, VI X, VI Y, VI S, VI E, VI L, VI R) { // 0 = small, 1 = big;
N = n;
M = X.size();
Q = S.size(); VI A(Q, 0);
for(int i = 0; i < M; i++) {
if(X[i] > Y[i]) swap(X[i], Y[i]);
sml[X[i]].pb(Y[i]);
big[Y[i]].pb(X[i]);
}
dsu.init(); memset(parent, -1, sizeof parent);
for(int u = 0; u < n; u++) {
for(auto it : big[u]) {
int v = dsu.find(it);
if(v == u) continue;
adj[1][u].pb(v);
parent[1][0][v] = u;
dsu.join(u, v);
}
}
dsu.init();
for(int u = n-1; u >= 0; u--) {
for(auto it : sml[u]) {
int v = dsu.find(it);
if(v == u) continue;
adj[0][u].pb(v);
parent[0][0][v] = u;
dsu.join(u, v);
}
}
tym = 0; dfs(0, 0);
tym = 0; dfs(n-1, 1);
for(int i = 1; 1 << i < n; i++) {
for(int j = 0; j < n; j++) {
if(parent[0][i-1][j] != -1) parent[0][i][j] = parent[0][i-1][parent[0][i-1][j]];
if(parent[1][i-1][j] != -1) parent[1][i][j] = parent[1][i-1][parent[1][i-1][j]];
}
}
int aux[maxn];
for(int i = 0; i < n; i++) aux[tour[1][i]] = i;
for(int i = 0; i < n; i++) ds.insert(i, aux[tour[0][i]]);
for(int i = 0; i < Q; i++) {
int u = S[i], v = E[i];
for(int j = 18; j >= 0; j--)
if(parent[0][j][u] != -1 && parent[0][j][u] >= L[i]) u = parent[0][j][u];
for(int j = 18; j >= 0; j--)
if(parent[1][j][v] != -1 && parent[1][j][v] <= R[i]) v = parent[1][j][v];
ds.query(st[0][u], st[1][v], ed[0][u], ed[1][v], i);
//cout << st[0][u] << " " << ed[0][u] << "\t\t" << st[1][v] << " " << ed[1][v] << endl;
} ds.process();
for(int i = 0; i < Q; i++) A[i] = ds.ans[i] > 0;
return A;
}
