#include "werewolf.h"
#include <bits/stdc++.h>
#define f first
#define s second
using namespace std;
const int N = 4e5 + 69;
const int M = 20 * N;
/*
g++ werewolf.cpp werewolf.h grader.cpp
./a.out
*/
int p[N], sz[N], par[N], vis[N];
vector<pair<int, int>> t[N];
vector<pair<int, int>> qs[N][2];
vector<int> g[N], dsu[2 * N][2];
int tin1[N], tout1[N], timer, tin2[N], tout2[N];
int rt[N], lc[M], rc[M], st[M], cs[N], node, x[N], y[N];
pair<int, int> str[N], ed[N];
int root(int v) {
if (p[v] == v)
return v;
return p[v] = root(p[v]);
}
void dfs(int v, int t) {
if (t == 0) {
tin1[v] = ++timer;
x[v] = tin1[v];
}
else {
tin2[v] = ++timer;
y[v] = tin2[v];
}
for (auto u : dsu[v][t])
dfs(u, t);
if (t == 0)
tout1[v] = timer;
else
tout2[v] = timer;
}
void modify(int v, int v1, int tl, int tr, int p) {
if (tl == tr)
st[v] = 1;
else {
int mid = (tl + tr) / 2;
if (p <= mid) {
lc[v] = ++node;
rc[v] = rc[v1];
modify(lc[v], lc[v1], tl, mid, p);
}
else {
rc[v] = ++node;
lc[v] = lc[v1];
modify(rc[v], rc[v1], mid + 1, tr, p);
}
st[v] = st[lc[v]] + st[rc[v]];
}
}
int get(int v, int tl, int tr, int l, int r) {
if (tl > r || tr < l)
return 0;
else if (tl >= l && tr <= r)
return st[v];
else {
int mid = (tl + tr) / 2;
return get(lc[v], tl, mid, l, r) + get(rc[v], mid + 1, tr, l, r);
}
}
vector<int> check_validity(int n, vector<int> u, vector<int> v, vector<int> s, vector<int> e, vector<int> l, vector<int> r) {
int q = s.size();
int m = u.size();
vector<int> ans(q);
for (int i = 0;i < m;i++) {
++u[i], ++v[i];
g[u[i]].push_back(v[i]);
g[v[i]].push_back(u[i]);
}
for (int i = 0;i < q;i++) {
l[i]++, r[i]++;
s[i]++, e[i]++;
}
for (int i = 1;i <= 2 * n;i++) {
p[i] = i;
sz[i] = 1;
}
for (int i = 0;i < q;i++) {
qs[l[i]][0].push_back({r[i], i});
qs[r[i]][1].push_back({l[i], i});
}
node = n;
for (int i = n;i >= 1;i--) {
vis[i] = 1;
++node;
p[i] = node;
sz[node] = 2;
dsu[node][0].push_back(i);
for (auto j : g[i]) {
if (vis[j]) {
int x = root(j);
int y = root(node);
if (x != y) {
dsu[node][0].push_back(x);
p[x] = node;
}
}
}
}
assert(node == 2 * n);
dfs(node, 0);
node = n;
for (int i = 1;i <= 2 * n;i++) {
vis[i] = 0;
p[i] = i;
sz[i] = 1;
}
for (int i = 1;i <= n;i++) {
vis[i] = 1;
++node;
p[i] = node;
sz[node] = 2;
dsu[node][1].push_back(i);
for (auto j : g[i]) {
if (vis[j]) {
int x = root(j);
int y = root(node);
if (x != y) {
dsu[node][1].push_back(x);
p[x] = node;
}
}
}
}
assert(node == 2 * n);
timer = 0;
dfs(node, 1);
for (int i = 1;i <= n;i++) {
cs[x[i]] = y[i];
}
node = 0;
for (int i = 2 * n;i >= 1;i--) {
rt[i] = rt[i + 1];
if (cs[i] > 0) {
int nr = ++node;
modify(nr, rt[i + 1], 1, N, cs[i]);
rt[i] = nr;
}
}
node = n;
for (int i = 1;i <= 2 * n;i++) {
p[i] = i, sz[i] = 1;
vis[i] = 0;
}
for (int i = n;i >= 1;i--) {
vis[i] = 1;
++node;
p[i] = node;
sz[node] = 2;
for (auto j : g[i]) {
if (vis[j]) {
int x = root(j);
int y = root(node);
if (x != y)
p[x] = node;
}
}
for (auto j : qs[i][0]) {
int ind = j.s;
int x = root(s[ind]);
str[ind] = {tin1[x], tout1[x]};
}
}
node = n;
for (int i = 1;i <= 2 * n;i++) {
p[i] = i, sz[i] = 1;
vis[i] = 0;
}
for (int i = 1;i <= n;i++) {
vis[i] = 1;
++node;
p[i] = node;
sz[node] = 2;
for (auto j : g[i]) {
if (vis[j]) {
int x = root(j);
int y = root(node);
if (x != y)
p[x] = node;
}
}
for (auto j : qs[i][1]) {
int ind = j.s;
int x = root(e[ind]);
ed[ind] = {tin2[x], tout2[x]};
}
}
for (int i = 0;i < q;i++) {
int x1 = str[i].f, y1 = str[i].s;
int x2 = ed[i].f, y2 = ed[i].s;
//da li se nesto pojavljuje u ovom pravougaoniku
int r = get(rt[x1], 1, N, x2, N);
r -= get(rt[x1], 1, N, y2 + 1, N);
r -= get(rt[y1 + 1], 1, N, x2, N);
r += 2 * get(rt[y1 + 1], 1, N, y2 + 1, N);
ans[i] = (r > 0);
}
return ans;
}
/*
6 6 3
5 1
1 2
2 5
1 3
3 4
0 3
4 2 1 2
4 2 2 2
5 4 3 4
*/
