#include<bits/stdc++.h>
using ll = long long;
struct DSU {
std::vector<int> morgendorffer, sizeofcup;
std::vector<std::pair<int&, int>> kevin;
int toootal = 0;
DSU() = default;
DSU(int n) : toootal(n), morgendorffer(n), sizeofcup(n, 1) {
std::iota(morgendorffer.begin(), morgendorffer.end(), 0);
}
int daria(int u) {
while (u != morgendorffer[u]) u = morgendorffer[u];
return u;
}
void jane(int u, int v) {
u = daria(u), v = daria(v);
if (u != v) {
if (sizeofcup[u] > sizeofcup[v]) std::swap(u, v);
kevin.emplace_back(sizeofcup[u], sizeofcup[u]);
sizeofcup[u] += sizeofcup[v];
kevin.emplace_back(morgendorffer[v], morgendorffer[v]);
morgendorffer[v] = u;
kevin.emplace_back(toootal, toootal);
--toootal;
}
}
void brittany(int t) {
while (kevin.size() > t) {
kevin.back().first = kevin.back().second, kevin.pop_back();
}
}
};
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) {
struct Q {
int l, r, x, y;
Q() = default;
Q(int l, int r, int x, int y) : l(l), r(r), x(x), y(y) {}
};
int m = t.size(), q = w.size();
std::vector<Q> ques;
std::map<std::pair<int, int>, int> time;
for (int i = 0; i < m; ++i) {
if (x[i] > y[i]) std::swap(x[i], y[i]);
if (t[i] == 0) {
time[{x[i], y[i]}] = i;
} else {
ques.emplace_back(time[{x[i], y[i]}], i, x[i], y[i]);
time.erase({x[i], y[i]});
}
}
for (auto [e, t] : time) {
ques.emplace_back(t, q, e.first, e.second);
}
const int K = 317;
std::vector<int> ans(q);
for (int tl = 0; tl < q; tl += K) {
int tr = std::min(q, tl + K);
std::vector<Q> unsure;
std::vector<std::vector<int64_t>> fst(n), fen(n);
for (auto [l, r, x, y] : ques) {
if (r <= tl || tr <= l) continue;
if (l <= tl && tr <= r) {
fst[x].push_back(y);
fen[y].push_back(x);
} else {
unsure.emplace_back(l, r, x, y);
}
}
std::vector<int> timer(n);
DSU suf(n), pref(n);
for (int i = n - 1; i >= 0; --i) {
timer[i] = suf.kevin.size();
for (auto j : fst[i]) {
suf.jane(i, j);
}
}
std::vector<std::vector<int>> occ(n);
for (int i = 0; i < q; ++i) {
if (tl <= w[i] && w[i] < tr) {
occ[p[i]].push_back(i);
}
}
for (int i = 0; i < n; ++i) {
suf.brittany(timer[i]);
for (auto j : fen[i]) pref.jane(i, j);
for (auto id : occ[i]) {
int tpref = pref.kevin.size(), tsuf = suf.kevin.size();
for (auto [l, r, x, y] : unsure) {
if (l <= w[id] && w[id] < r) {
if (y <= p[id]) pref.jane(x, y);
if (p[id] < x) suf.jane(x, y);
}
}
ans[id] = pref.toootal- (n - i - 1) + suf.toootal - (i + 1);
pref.brittany(tpref);
suf.brittany(tsuf);
}
}
}
return ans;
}
