#include <bits/stdc++.h> #define z exit(0) #include "werewolf.h" using namespace std; const int N = 2e5 + 5, dN = 4e5 + 5, oN = 1600005, M = 4e5 + 5; vector<int> g[2][dN], s[oN]; int X[M], Y[M], id[M], p[2][dN], W[2][dN], up[2][dN][18], d[2][dN], tin[2][dN], tout[2][dN], arr[2][dN], ti[2], n, L1, R1, L2, R2; bool cmp0(int i, int j){ return min(X[i], Y[i]) > min(X[j], Y[j]);} bool cmp1(int i, int j){ return max(X[i], Y[i]) < max(X[j], Y[j]);} int fp(int x, int u){ return u == p[x][u] ? u : p[x][u] = fp(x, p[x][u]);} int kth(int x, int u, int k){ for(int j = 17; ~j; --j) if(k>>j&1) u = up[x][u][j]; return u;} void bld(int ind, int low, int high){ if(low == high){ s[ind] = vector<int>(1, arr[0][low]); return; } int mid = (low + high)>>1; bld(ind<<1, low, mid); bld(ind<<1|1, mid+1, high); merge(s[ind<<1].begin(), s[ind<<1].end(), s[ind<<1|1].begin(), s[ind<<1|1].end(), back_inserter(s[ind])); } int qry(int ind, int low, int high){ if(low > R1 || high < L1) return 0; if(L1 <= low && high <= R1) return upper_bound(s[ind].begin(), s[ind].end(), R2) - lower_bound(s[ind].begin(), s[ind].end(), L2); int mid = (low + high)>>1; return qry(ind<<1, low, mid) + qry(ind<<1|1, mid+1, high); } void dfs(int x, int u, int p){ up[x][u][0] = p; tin[x][u] = ti[x]++; if(u != p) d[x][u] = d[x][p] + 1; for(int j = 1; j<18; ++j) up[x][u][j] = up[x][up[x][u][j-1]][j-1]; for(int v: g[x][u]) dfs(x, v, u); tout[x][u] = ti[x]-1; } vector<int> check_validity(int _n, vector<int> XX, vector<int> YY, vector<int> S, vector<int> E, vector<int> L, vector<int> R){ // vector<int> ttt = {1, 0, 0}; return ttt; // int m = XX.size(), n = _n; for(int i = 0; i<m; ++i) X[i] = XX[i], Y[i] = YY[i], id[i] = i; for(int i = 0; i<2*n; ++i) p[0][i] = p[1][i] = i; int nn[2] = {n, n}; for(int x = 0; x<2; ++x){ if(!x) sort(id, id+m, cmp0); else sort(id, id+m, cmp1); for(int i = 0; i<m; ++i){ int u = X[id[i]], v = Y[id[i]]; if(fp(x, u) != fp(x, v)){ g[x][nn[x]].push_back(fp(x, u)); p[x][fp(x, u)] = nn[x]; g[x][nn[x]].push_back(fp(x, v)); p[x][fp(x, v)] = nn[x]; if(!x) W[x][nn[x]++] = min(X[id[i]], Y[id[i]]); else W[x][nn[x]++] = max(X[id[i]], Y[id[i]]); } } ti[x] = 0; fill(arr[x], arr[x]+nn[x], -1); dfs(x, nn[x]-1, nn[x]-1); for(int i = 0; i<n; ++i) arr[x][tin[x][i]] = i; } map<int,int> mp; for(int i = 0; i<nn[1]; ++i) if(0 <= arr[1][i] && arr[1][i] < n) mp[arr[1][i]] = i; for(int i = 0; i<nn[0]; ++i){ if(0 <= arr[0][i] && arr[0][i] < n) arr[0][i] = mp[arr[0][i]]; } bld(1, 0, nn[0]-1); int q = S.size(); vector<int> Ans(q); for(int i = 0; i<q; ++i){ int u = S[i], v = E[i], anc_u = -1, anc_v = -1; int low = 0, high = d[0][u]; while(low <= high){ int mid = (low + high)>>1; int anc = kth(0, u, mid); if(W[0][anc] >= L[i]) low = mid+1, anc_u = anc; else high = mid-1; } low = 0; high = d[1][v]; while(low <= high){ int mid = (low + high)>>1; int anc = kth(1, v, mid); if(W[1][anc] <= R[i]) low = mid+1, anc_v = anc; else high = mid-1; } if(anc_u == -1 || anc_v == -1){ Ans[i] = 0; continue;} L1 = tin[0][anc_u]; R1 = tout[0][anc_u]; L2 = tin[1][anc_v]; R2 = tout[1][anc_v]; int cnt_qry = qry(1, 0, nn[0]-1); if(cnt_qry) Ans[i] = 1; else Ans[i] = 0; } return Ans; }