#include "werewolf.h"
#include<iostream>
#include<utility>
#include<algorithm>
#include<vector>
using namespace std;
namespace{
int n, q;
vector<int> bases;
struct node{
int par, sz, lid, rid;
node(int a, int b, int c, int d){
par = a;
sz = b;
lid = c;
rid = d;
}
};
struct dsust{
vector<node> dsu;
vector<int> l, r, w, vec, pos;
vector<vector<int>> st;
dsust(){
for(int i = 0; i <= n; i++) dsu.push_back(node(i, 1, i, i));
l.resize(n + 1);
r.resize(n + 1);
w.resize(n + 1);
vec.resize(n + 1);
pos.resize(n + 1);
st.resize(19, vector<int>(n + 1));
fill(l.begin(), l.end(), -1);
fill(r.begin(), r.end(), -1);
}
int query(int x){
if(x == dsu[x].par) return x;
dsu[x].par = query(dsu[x].par);
return dsu[x].par;
}
void unite(int a, int b, int val){
a = query(a);
b = query(b);
if(a == b) return;
if(dsu[a].sz < dsu[b].sz) swap(a, b);
dsu[b].par = a;
dsu[a].sz += dsu[b].sz;
w[dsu[a].rid] = val;
r[dsu[a].rid] = dsu[b].lid;
l[dsu[b].lid] = dsu[a].rid;
dsu[a].rid = dsu[b].rid;
}
void build(){
int cur = dsu[query(1)].lid;
for(int i = 1; i <= n; i++){
vec[i] = cur;
pos[cur] = i;
st[0][i] = w[cur];
cur = r[cur];
}
for(int i = 1; i < 19; i++){
for(int j = 1; j < n; j++){
st[i][j] = max(st[i - 1][j], st[i - 1][min(n - 1, j + (1 << (i - 1)))]);
}
}
}
int query(int ql, int qr){
int len = qr - ql + 1;
return max(st[bases[len]][ql], st[bases[len]][qr - (1 << bases[len]) + 1]);
}
pair<int, int> get_rng(int id, int val){
pair<int, int> ans;
id = pos[id];
int bsl = id, bsr = n;
while(bsl < bsr){
int mid = ((bsl + bsr) >> 1) + 1;
if(query(id, mid - 1) > val) bsr = mid - 1;
else bsl = mid;
}
ans.second = bsl;
bsl = 1, bsr = id;
while(bsl < bsr){
int mid = (bsl + bsr) >> 1;
if(query(mid, id - 1) > val) bsl = mid + 1;
else bsr = mid;
}
ans.first = bsl;
return ans;
}
};
struct bit{
vector<int> vec;
bit(int _n){
vec.resize(_n + 1);
}
void modify(int pos){
while(pos <= n){
vec[pos]++;
pos += (pos & -pos);
}
}
int query(int pos){
int ans = 0;
while(pos > 0){
ans += vec[pos];
pos -= (pos & -pos);
}
return ans;
}
};
}
std::vector<int> check_validity(int N, std::vector<int> X, std::vector<int> Y, std::vector<int> S, std::vector<int> E, std::vector<int> L, std::vector<int> R) {
n = N;
q = (int)S.size();
bases.resize(n);
int now = 0;
for(int i = 1; i < n; i++){
if((1 << (now + 1)) <= i) now++;
bases[i] = now;
}
int m = (int)X.size();
vector<pair<pair<int, int>, int>> maxedges, minedges;
auto cmp = [&](pair<pair<int, int>, int> a, pair<pair<int, int>, int> b){
return a.second < b.second;
};
for(int i = 0; i < m; i++){
X[i]++;
Y[i]++;
maxedges.push_back(make_pair(make_pair(X[i], Y[i]), -min(X[i], Y[i])));
minedges.push_back(make_pair(make_pair(X[i], Y[i]), max(X[i], Y[i])));
}
sort(maxedges.begin(), maxedges.end(), cmp);
sort(minedges.begin(), minedges.end(), cmp);
dsust maxst = dsust(), minst = dsust();
for(auto &[x, val]: maxedges){
auto &[u, v] = x;
maxst.unite(u, v, val);
}
for(auto &[x, val]: minedges){
auto &[u, v] = x;
minst.unite(u, v, val);
}
maxst.build();
minst.build();
vector<pair<int, int>> qpos(q);
vector<vector<pair<int, int>>> sweep(n + 1);
vector<int> ans(q);
for(int i = 0; i < q; i++){
S[i]++;
E[i]++;
L[i]++;
R[i]++;
qpos[i] = minst.get_rng(E[i], R[i]);
auto [l, r] = maxst.get_rng(S[i], -L[i]);
sweep[l - 1].emplace_back(i, -1);
sweep[r].emplace_back(i, 1);
}
bit b(n);
for(int i = 1; i <= n; i++){
b.modify(minst.pos[maxst.vec[i]]);
for(auto &[id, val]: sweep[i]){
ans[id] += val * (b.query(qpos[id].second) - b.query(qpos[id].first - 1));
}
}
vector<int> anss;
for(int i = 0; i < q; i++){
if(ans[i] > 0) anss.push_back(1);
else anss.push_back(0);
}
return anss;
}
// g++ -std=c++17 -fsanitize=undefined -fsanitize=address -Wall -Wextra -Wshadow grader.cpp werewolf.cpp -o run
/*
6 6 3
5 1
1 2
1 3
3 4
3 0
5 2
4 2 1 2
4 2 2 2
5 4 3 4
*/
