#include <bits/stdc++.h> #include "werewolf.h" using namespace std; // #define int long long #define eb emplace_back #define mp make_pair #define pb push_back #define pp pop_back #define endl '\n' #define ff first #define ss second #define stop exit(0) #define sz(x) (int)x.size() #define pause system("pause") #define all(x) (x).begin(), (x).end() #define deb(x) cout << #x << "-" << x << endl mt19937 rng(chrono::steady_clock::now().time_since_epoch().count()); typedef char chr; typedef string str; typedef long long ll; typedef vector<int> vii; typedef pair<int, int> pii; const long long INF = LLONG_MAX; const int inf = INT_MAX; const int mod = 998244353; const int MOD = 1000000007; const int dx[] = {-1,0,1,0}; const int dy[] = {0,1,0,-1}; const double PI = 2 * acos(0.0); const int M = 2e5+5; vector <vii> g(M),v(M); int par[M]; int cur; int in[M],out[M]; int x[M],y[M]; pii Lr[M],Rr[M]; int px[M],py[M]; int Arr[M]; vector <vii> t(M*4); void cleardsu() { 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 (a == b) return; par[a] = par[b]; v[a].pb(b); v[b].pb(a); } void dfs(int x, int p) { in[x] = ++cur; for (auto to:v[x]) { if (to == p) continue; dfs(to,x); } out[x] = cur; } vii comb(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] = comb(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--) { unionset(N+i,i); for (auto to: g[i]) { if (to >= i) { unionset(N+i,to); } } } dfs(N,N); iota(x,x+N,0); sort(x,x+N,[](int a, int b) { return in[a]<in[b]; }); for (int i = 0; i < N; i++) { int l = 0, r = N-1; int tl=-1; while (l <= r) { int mid = (l+r)/2; if (in[x[mid]] >= in[i+N]) { r = mid - 1; tl = mid; } else { l = mid + 1; } } l = 0; r = N-1; int tr = -1; while (l <= r) { int mid = (l+r)/2; if (in[x[mid]] <= out[i+N]) { l = mid + 1; tr = mid; } else { r = mid - 1; } } Lr[i] = mp(tl,tr); } cleardsu(); for (int i = 0; i < N; i++) { for (auto to:g[i]) { if (to <= i) { unionset(N+i,to); } } } dfs(2*N-1,2*N-1); iota(y,y+N,0); sort(y,y+N,[](int a, int b) { return in[a]<in[b]; }); for (int i = 0; i < N; i++) { int l = 0, r = N-1; int tl=-1; while (l <= r) { int mid = (l+r)/2; if (in[y[mid]] >= in[i+N]) { r = mid - 1; tl = mid; } else { l = mid + 1; } } l = 0; r = N-1; int tr = -1; while (l <= r) { int mid = (l+r)/2; if (in[y[mid]] <= out[i+N]) { l = mid + 1; tr = mid; } else { r = mid - 1; } } Rr[i] = mp(tl,tr); } 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 < sz(S)) { int lx = Lr[L[q]].ff; int rx = Lr[L[q]].ss; int ly = Rr[R[q]].ff; int ry = Rr[R[q]].ss; if (S[q] < L[q] || E[q] > R[q]) { A[q] = 0; q++; continue; } A[q] = getans(1,0,N-1,lx,rx,ly,ry); q++; } return A; }