#include "werewolf.h"
#include <iostream>
#include <vector>
#include <algorithm>
#include <cstdio>
#include <cmath>
#include <cstdlib>
#include <unordered_set>
#include <cstring>
#include <stack>
using namespace std;
struct DSU
{
vector<int> a;
DSU(int n)
{
a.resize(n);
for (int i = 0; i < n; ++i) a[i] = i;
}
int root(int x)
{
return (x == a[x] ? x : a[x] = root(a[x]));
}
void merge(int x, int y) // root[y] = x
{
a[root(y)] = root(x);
}
bool same(int x, int y)
{
return root(x) == root(y);
}
};
struct IT
{
int n;
vector< unordered_set<int> > a;
IT(int _n)
{
n = _n;
a.resize(4*n);
}
void update(int x, int from, int to, int root, int s0, int e1, bool add)
{
if (to < s0 || e1 < from) return;
if (from <= s0 && e1 <= to) {
if (add) a[root].insert(x);
else a[root].erase( a[root].find(x) );
return;
}
int m = (s0 + e1) / 2;
update(x, from, to, 2 * root, s0, m, add);
update(x, from, to, 2 * root + 1, m+1, e1, add);
}
void addX(int x, int from, int to)
{
update(x, from, to, 1, 0, n-1, 1);
}
void removeX(int x, int from, int to)
{
update(x, from, to, 1, 0, n-1, 0);
}
void get(int pos, int root, int s0, int e1, vector<int>& ans)
{
for (int i : a[root]) ans.push_back(i);
if (s0 == e1) return;
int m = (s0 + e1) / 2;
if (pos <= m) get(pos, root * 2, s0, m, ans);
else get(pos, root * 2 + 1, m+1, e1, ans);
}
void get(int pos, vector<int>& ans)
{
get(pos, 1, 0, n-1, ans);
}
};
void dfsTour(int u, vector< vector<int> > &graph, vector<int>& s, vector<int> &e, int &cur)
{
s[u] = ++cur;
// cerr << u << endl;
for (int v : graph[u]) dfsTour(v, graph, s, e, cur);
e[u] = cur;
}
void dfsEverything(int u, vector< vector<int> > &tree1, vector< vector<int> > &queries, vector<int> &S, vector<int> &startS, vector<int>& endS, vector<int> &ans, IT &it)
{
// add queries
for (int qi : queries[u]) {
it.addX(qi, startS[S[qi]], endS[S[qi]]);
}
// process queries
vector<int> finishedQueries;
it.get(startS[u], finishedQueries);
for (int qi : finishedQueries) {
ans[qi] = 1;
it.removeX(qi, startS[S[qi]], endS[S[qi]]);
}
// process children
for (int v : tree1[u]) dfsEverything(v, tree1, queries, S, startS, endS, ans, it);
// remove queries
for (int qi : queries[u]) {
if (ans[qi] == 1) continue;
it.removeX(qi, startS[S[qi]], endS[S[qi]]);
ans[qi] == 0; // should be redundant
}
}
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 logN = log2(N) + 1;
vector<int> ans(S.size(), 0);
// Convert X & Y -> adjList
vector< vector<int> > graph(N); // bidirectional
for (int i = 0; i < X.size(); ++i) {
graph[X[i]].push_back(Y[i]);
graph[Y[i]].push_back(X[i]);
}
// Create tree 1 (<= x)
vector< vector<int> > tree1(N);
DSU dsu1(N);
for (int u = 0; u < N; ++u) {
for (int v : graph[u]) {
if (v > u) continue;
if (dsu1.same(u, v)) continue;
tree1[u].push_back(dsu1.root(v));
// cerr << u << " -> " << dsu1.root(v) << endl;
dsu1.merge(u, v); // order matters!
}
}
// Create par1
vector< vector<int> > par1(logN + 1, vector<int>(N));
for (int u = 0; u < N; ++u) {
for (int v : tree1[u]) {
par1[0][v] = u;
}
}
par1[0][N-1] = -1;
// for (int i = 0; i < N; ++i) cerr << par1[0][i] << ' '; cerr << endl;
for (int i = 1; i <= logN; ++i) {
for (int u = 0; u < N; ++u) {
int v = par1[i-1][u];
par1[i][u] = (v == -1) ? -1 : par1[i-1][v];
}
}
// Create tree 2 (>= x)
vector< vector<int> > tree2(N);
DSU dsu2(N);
for (int u = N-1; u >= 0; --u) {
for (int v : graph[u]) {
if (v < u) continue;
if (dsu2.same(u, v)) continue;
tree2[u].push_back(dsu2.root(v));
dsu2.merge(u, v); // order matters!
}
}
// Create par2
vector< vector<int> > par2(logN + 1, vector<int>(N));
for (int u = 0; u < N; ++u) {
for (int v : tree2[u]) {
par2[0][v] = u;
}
}
par2[0][0] = -1;
// for (int i = 0; i < N; ++i) cerr << par2[0][i] << ' '; cerr << endl;
for (int i = 1; i <= logN; ++i) {
for (int u = 0; u < N; ++u) {
int v = par2[i-1][u];
par2[i][u] = (v == -1) ? -1 : par2[i-1][v];
}
}
// Re-write queries
vector< vector<int> > queries(N);
for (int qi = 0; qi < S.size(); ++qi) {
// S[i] <- L[i], tree2
for (int lg = logN; lg >= 0; --lg) {
int u = par2[lg][S[qi]];
if (u >= 0 && u >= L[qi]) S[qi] = u;
}
// E[i] <- R[i], tree1
for (int lg = logN; lg >= 0; --lg) {
int u = par1[lg][E[qi]];
if (u >= 0 && u <= R[qi]) E[qi] = u;
}
// cerr << S[qi] << ' ' << E[qi] << endl;
queries[E[qi]].push_back(qi);
}
// Check with trees
// Tree 1: dfs
// Tree 2: Euler tour + IT
// Euler tour for tree2
int cur = -1;
vector<int> startS(S.size()), endS(S.size());
// cerr << endl;
dfsTour(0, tree2, startS, endS, cur);
// cerr << startS[5] << ' ' << endS[5] << endl;
// IT for tree2
IT intervalTree(N);
// dfs for tree1
dfsEverything(N-1, tree1, queries, S, startS, endS, ans, intervalTree);
return ans;
}
