#include <bits/stdc++.h> #include "werewolf.h" using namespace std; #define pb push_back #define sz(x) (int)x.size() #define all(x) (x).begin(), (x).end() typedef vector<int> vii; typedef pair<int, int> pii; const int M = 2e5+5; vector <vii> g(M),v(M); int par[M]; int cur; int in1[M],out1[M]; int in2[M],out2[M]; int x[M],y[M]; pii Lr[M],Rr[M]; int px[M],py[M]; int Arr[M]; int up1[20][M],up2[20][M]; vector <vii> t(M*4); void cleardsu() { cur = 0; for (int i = 0; i < M; i++) { par[i] = i; v[i].clear(); } } int getpar(int x) { if (x == par[x]) return x; return par[x] = getpar(par[x]); } void unionset(int a, int b) { a = getpar(a); b = getpar(b); if (b == a) return; par[b] = a; v[a].pb(b); v[b].pb(a); } void dfs1(int x, int p) { in1[x] = ++cur; up1[0][x] = p; for (int i = 1; i <= 18; i++) { up1[i][x] = up1[i-1][up1[i-1][x]]; } for (auto to:v[x]) { if (to == p) continue; dfs1(to,x); } out1[x] = cur; } void dfs2(int x, int p) { in2[x] = ++cur; up2[0][x] = p; for (int i = 1; i <= 18; i++) { up2[i][x] = up2[i-1][up2[i-1][x]]; } for (auto to:v[x]) { if (to == p) continue; dfs2(to,x); } out2[x] = cur; } vii merge(vii a, vii b) { vii res; int pos1 = 0; int pos2 = 0; while (pos1 < sz(a) && pos2 < sz(b)) { if (a[pos1] < b[pos2]) { res.pb(a[pos1]); pos1++; } else { res.pb(b[pos2]); pos2++; } } while (pos2 < sz(b)) { res.pb(b[pos2]); pos2++; } while (pos1 < sz(a)) { res.pb(a[pos1]); pos1++; } return res; } void build(int node, int l, int r) { if (l == r) { t[node].pb(Arr[l]); return; } int mid = (l+r)/2; build (node*2,l,mid); build(node*2+1,mid+1,r); t[node] = merge(t[node*2],t[node*2+1]); } bool getans(int node, int l, int r, int lx, int rx, int ly, int ry) { if (r < lx || l > rx) return 0; if (l >= lx && r <= rx) { auto it = lower_bound(all(t[node]),ly); return (it != t[node].end() && *it <= ry); } int mid = (l+r)/2; return (getans(node*2,l,mid,lx,rx,ly,ry) || getans(node*2+1,mid+1,r,lx,rx,ly,ry)); } 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 Q = S.size(); vector<int> A(Q); for (int i = 0; i < Q; ++i) { A[i] = 0; } for (int i = 0; i < sz(X); i++) { g[X[i]].pb(Y[i]); g[Y[i]].pb(X[i]); } cleardsu(); for (int i = N-1; i >= 0; i--) { for (auto to: g[i]) { if (to >= i) { unionset(i,to); } } } dfs1(0,0); for (int i = 0; i < N; i++) { x[in1[i]] = i; } cleardsu(); for (int i = 0; i < N; i++) { for (auto to:g[i]) { if (to <= i) { unionset(i,to); } } } dfs2(N-1,N-1); for (int i = 0; i < N; i++) { y[in2[i]] = i; } cleardsu(); for (int i = 0; i < N; i++) { px[x[i]] = i; } for (int i = 0; i < N; i++) { py[y[i]] = i; } for (int i = 0; i < N; i++) { Arr[px[i]] = py[i]; } build (1,0,N-1); int q = 0; while (q < Q) { int st = S[q]; int ed = E[q]; for (int i = 18; i >= 0; i--) { if (up1[i][st] >= L[q]) st = up1[i][st]; } for (int i = 18; i >= 0; i--) { if (up2[i][ed] <= R[q]) ed = up2[i][ed]; } int lx = in1[st]; int rx = out1[st]; int ly = in2[ed]; int ry = out2[ed]; if (st < L[q] || ed > R[q]) { A[q] = 0; q++; continue; } A[q] = getans(1,0,N-1,lx,rx,ly,ry); q++; } return A; }