#include "collapse.h"
#include <bits/stdc++.h>
#define Loop(x, l, r) for (ll x = (l); x < (r); ++x)
typedef long long ll;
typedef std::pair<int,int> pii;
using namespace std;
const int N = 100'010;
namespace dsu {
int par[N];
int sz[N];
vector<pii> his;
int cnt;
bool rec;
void init() {
fill(par, par+N, -1);
fill(sz, sz+N, 1);
his.clear();
cnt = 0;
rec = 0;
}
int rt(int v) { return par[v] == -1? v: rt(par[v]); }
void unite(int v, int u) {
v = rt(v);
u = rt(u);
if (v == u)
return;
if (sz[v] < sz[u])
swap(v, u);
par[u] = v;
sz[v] += sz[u];
++cnt;
if (rec)
his.emplace_back(v, u);
}
void rollback() {
while (his.size()) {
auto [v, u] = his.back();
his.pop_back();
--cnt;
sz[v] -= sz[u];
par[u] = -1;
}
rec = 0;
}
}
vector<pair<int,pii>> A[N], T[N];
void make_graph(vector<int> t, vector<int> V, vector<int> U)
{
set<pair<pii,int>> e;
Loop (i,0,t.size()) {
int v = V[i], u = U[i];
if (v > u)
swap(v, u);
if (t[i]) {
auto it = e.lower_bound({{v, u}, -1});
int l = it->second, r = i;
A[v].push_back({u, {l,r}});
T[u].push_back({v, {l,r}});
e.erase(it);
} else {
e.insert({{v, u}, i});
}
}
for (auto [dard, l] : e) {
auto [v, u] = dard;
int r = t.size();
A[v].push_back({u, {l,r}});
T[u].push_back({v, {l,r}});
}
}
const int S = 1000;
int ans[N];
std::vector<int> simulateCollapse(
int n,
std::vector<int> T,
std::vector<int> X,
std::vector<int> Y,
std::vector<int> W,
std::vector<int> P
) {
make_graph(T, X, Y);
vector<int> Q(W.size());
iota(Q.begin(), Q.end(), 0);
sort(Q.begin(), Q.end(), [&](int i, int j) { return W[i] < W[j]; });
for (int l = 0, r = 0; l < W.size(); l = r) {
while (r < W.size() && W[Q[r]] - W[Q[l]] <= S)
++r;
vector<int> Q2;
Loop (i,l,r)
Q2.push_back(Q[i]);
sort(Q2.begin(), Q2.end(), [&](int i, int j) { return P[i] < P[j]; });
Loop (phase,0,2) {
dsu::init();
vector<pair<pii,pii>> E;
int p = phase == 0? 0: n-1;
for (int q : Q2) {
while (phase == 0? p <= P[q]: p > P[q]) {
for (auto [u, t] : (phase == 0? ::T[p]: ::A[p])) {
if (t.first <= W[Q[l]] && W[Q[r-1]] < t.second) {
dsu::unite(p, u);
continue;
}
if (W[Q[r-1]] < t.first || t.second <= W[Q[l]])
continue;
E.push_back({{p,u},t});
}
p += phase == 0? 1: -1;
}
dsu::rec = 1;
for (auto [e, t] : E) {
if (t.first <= W[q] && W[q] < t.second)
dsu::unite(e.first, e.second);
}
ans[q] += dsu::cnt;
dsu::rollback();
}
reverse(Q2.begin(), Q2.end());
}
}
Loop (i,0,Q.size())
ans[i] = n - ans[i];
return vector<int>(ans, ans+Q.size());
}
