#include "werewolf.h"
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
struct DSU {
int n, id;
vector<int> sz, par, tpar, tid, val, tin, tout;
vector<vector<int>> adj, up;
DSU(int _n) {
n = id = _n;
sz = vector<int>(n, 1), par = vector<int>(n, -1);
tid = vector<int>(n), val = vector<int>(2*n-1, -1), tpar = vector<int>(2*n-1, -1);
tin = vector<int>(2*n-1), tout = vector<int>(2*n-1);
up = vector<vector<int>>(20, vector<int>(2*n-1, -1));
for (int i = 0; i < n; i++) par[i] = tid[i] = i;
}
int find(int x) { return par[x] == x ? x : par[x] = find(par[x]); }
bool connected(int x, int y) { return find(x) == find(y); }
bool join(int x, int y, int v) {
x = find(x), y = find(y);
if (connected(x, y)) return 0;
if (sz[x] < sz[y]) swap(x, y);
sz[x] += sz[y];
par[y] = x;
val[id] = v;
tpar[tid[x]] = tpar[tid[y]] = id;
tid[x] = id++;
return 1;
}
void complete() {
adj = vector<vector<int>>(2*n-1);
for (int i = 0; i < 2*n-1; i++) if (tpar[i] >= 0) adj[tpar[i]].push_back(i), up[0][i] = tpar[i];
for (int j = 1; j < 20; j++) for (int i = 0; i < 2*n-1; i++) if (up[j-1][i] != -1) up[j][i] = up[j-1][up[j-1][i]];
int timer = 0;
auto dfs = [&](auto dfs, int u, int d = 0) -> void {
//for (int i = 0; i < d; i++) cout << "\t";
//cout << u << " (" << val[u] << ") :" << endl;
tin[u] = timer;
for (int v : adj[u]) dfs(dfs, v, d+1);
tout[u] = timer++;
};
dfs(dfs, 2*n-2);
//cout << "tin: "; for (int x : tin) cout << x << " "; cout << endl;
//cout << "tout: "; for (int x : tout) cout << x << " "; cout << endl;
}
int getCord(int i) { return tout[i]; }
pair<int, int> getRange(int start, int to, bool less) {
int u = start;
for (int b = 19; b >= 0; b--) if (up[b][u] != -1) {
int v = up[b][u];
if ((!less && to <= val[v]) || (less && to >= val[v])) u = up[b][u];
}
//cout << start << " -> " << u << endl;
return {tin[u], tout[u]};
}
};
struct Node {
int l = 0, r = 0, sum = 0;
Node(int v = 0) { sum = v; }
Node(int _l, int _r);
};
vector<Node> t(1);
Node::Node(int _l, int _r) {
l = _l;
r = _r;
if (l) sum += t[l].sum;
if (r) sum += t[r].sum;
}
int new_node(Node node) {
t.push_back(node);
return t.size()-1;
}
int query(int id, int l, int r, int x, int y) {
if (!id || y <= l || r <= x) return 0;
if (x <= l && r <= y) return t[id].sum;
int m = (l+r)/2;
return query(t[id].l, l, m, x, y)+query(t[id].r, m, r, x, y);
}
int update(int id, int l, int r, int p, int val) {
if (r-l == 1) return new_node(Node(t[id].sum + val));
int m = (l+r)/2;
if (p < m) return new_node(Node(update(t[id].l, l, m, p, val), t[id].r));
else return new_node(Node(t[id].l, update(t[id].r, m, r, p, val)));
}
vector<int> xroot;
int N;
int rect(int x1, int x2, int y1, int y2) { // [x1, x2] [y1, y2]
return query(xroot[x2+1], 0, N, y1, y2+1)-query(xroot[x1], 0, N, y1, y2+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) {
int m = X.size();
N = 2*n;
vector<pair<int, int>> e;
for (int i = 0; i < m; i++) e.push_back(min(pair<int, int>{X[i], Y[i]}, pair<int, int>{Y[i], X[i]}));
sort(e.rbegin(), e.rend());
DSU dsuH(n);
for (int i = 0; i < m; i++) dsuH.join(e[i].first, e[i].second, e[i].first);
dsuH.complete();
for (int i = 0; i < m; i++) e[i] = max(pair<int, int>{X[i], Y[i]}, pair<int, int>{Y[i], X[i]});
sort(e.begin(), e.end());
DSU dsuW(n);
for (int i = 0; i < m; i++) dsuW.join(e[i].first, e[i].second, e[i].first);
dsuW.complete();
xroot = vector<int>(2*n+1);
vector<vector<int>> add(2*n);
for (int i = 0; i < n; i++) add[dsuH.getCord(i)].push_back(dsuW.getCord(i));
for (int i = 0; i < 2*n; i++) {
xroot[i+1] = xroot[i];
for (int j : add[i]) xroot[i+1] = update(xroot[i+1], 0, N, j, 1);
}
//cout << endl << "---" << endl << endl;
int q = S.size();
vector<int> ans(q);
for (int i = 0; i < q; ++i) {
if (S[i] < L[i] || E[i] > R[i]) continue;
auto [loH, hiH] = dsuH.getRange(S[i], L[i], 0);
auto [loW, hiW] = dsuW.getRange(E[i], R[i], 1);
//cout << "Query " << i+1 << ": " << endl;
//cout << loH << " " << hiH << endl;
//cout << "Human: "; for (int i = 0; i < n; i++) if (loH <= dsuH.getCord(i) && dsuH.getCord(i) <= hiH) cout << i << " "; cout << endl;
//cout << loW << " " << hiW << endl;
//cout << "Werewulf: "; for (int i = 0; i < n; i++) if (loW <= dsuW.getCord(i) && dsuW.getCord(i) <= hiW) cout << i << " "; cout << endl;
//cout << endl;
ans[i] = rect(loH, hiH, loW, hiW) > 0;
}
return ans;
}
