#include <bits/stdc++.h>
#include "collapse.h"
using namespace std;
vector<int> simulateCollapse(int N, vector<int> T, vector<int> X, vector<int> Y, vector<int> W, vector<int> P)
{
const int S = 320;
int C = X.size(), Q = W.size();
int cnt = 0;
vector<int> lab(N, -1);
vector<array<int, 2>> his;
auto init = [&]()
{
fill(lab.begin(), lab.end(), -1);
cnt = 0;
};
auto find = [&](int u) -> int
{
while (lab[u] >= 0)
u = lab[u];
return u;
};
auto unite = [&](int u, int v, bool keep)
{
u = find(u), v = find(v);
if (u == v)
{
if (keep)
his.push_back({-1, -1});
return;
}
if (lab[u] > lab[v])
swap(u, v);
if (keep)
his.push_back({v, lab[v]});
cnt++;
lab[u] += lab[v];
lab[v] = u;
};
auto restore = [&]()
{
while (his.size())
{
auto e = his.back();
his.pop_back();
if (~e[0])
{
--cnt;
int &p = lab[e[0]];
lab[p] -= e[1];
p = e[1];
}
}
};
vector<array<int, 2>> comp;
for (int i = 0; i < C; i++)
{
if (X[i] > Y[i])
swap(X[i], Y[i]);
comp.push_back({X[i], Y[i]});
}
sort(comp.begin(), comp.end());
comp.erase(unique(comp.begin(), comp.end()), comp.end());
int M = comp.size();
vector<int> pos(C);
for (int i = 0; i < C; i++)
{
T[i] ^= 1;
pos[i] = lower_bound(comp.begin(), comp.end(), array<int, 2>{X[i], Y[i]}) - comp.begin();
}
vector<array<int, 3>> queries;
vector<int> res(Q);
for (int i = 0; i < Q; i++)
{
queries.push_back({P[i], W[i], i});
res[i] = N;
}
sort(queries.begin(), queries.end(), [&](const auto &u, const auto &v)
{ return u[1] < v[1]; });
vector<bool> tog(M), cur(M), nw(M);
int ptr = 0;
for (int i = 0; i < C; i += S)
{
int l = i, r = min(C - 1, i + S - 1);
for (int j = l; j <= r; j++)
tog[pos[j]] = 1;
vector<int> add;
vector<array<int, 2>> cands;
for (int j = 0; j < M; j++)
if (!tog[j] && cur[j])
cands.push_back(comp[j]);
else if (tog[j])
add.push_back(j);
vector<array<int, 3>> ord;
while (ptr < Q && queries[ptr][1] <= r)
ord.push_back(queries[ptr++]);
sort(ord.begin(), ord.end());
sort(cands.begin(), cands.end(), [&](const auto &u, const auto &v)
{ return u[1] < v[1]; });
init();
int k = 0;
for (auto [x, d, id] : ord)
{
while (k < cands.size() && cands[k][1] <= x)
{
unite(cands[k][0], cands[k][1], 0);
k++;
}
for (int j = l; j <= d; j++)
nw[pos[j]] = T[j];
for (int id : add)
{
if (nw[id] && comp[id][1] <= x)
unite(comp[id][0], comp[id][1], 1);
nw[id] = cur[id];
}
res[id] -= cnt;
restore();
}
init();
reverse(ord.begin(), ord.end());
sort(cands.rbegin(), cands.rend());
k = 0;
for (auto [x, d, id] : ord)
{
while (k < cands.size() && cands[k][0] > x)
{
unite(cands[k][0], cands[k][1], 0);
k++;
}
for (int j = l; j <= d; j++)
nw[pos[j]] = T[j];
for (int id : add)
{
if (nw[id] && comp[id][0] > x)
unite(comp[id][0], comp[id][1], 1);
nw[id] = cur[id];
}
res[id] -= cnt;
restore();
}
for (int j = l; j <= r; j++)
{
tog[pos[j]] = 0;
cur[pos[j]] = T[j];
nw[pos[j]] = cur[pos[j]];
}
}
return res;
}
