#include "collapse.h" #include <bits/stdc++.h> using namespace std; #define ii pair<int,int> using ll = long long; const int nx = 100000 + 5; const int bl = 300; struct dak { vector<int> par, sz; // history as (type, index, old_value) // type 0 = par[idx] old value, type 1 = sz[idx] old value vector<tuple<int,int,int>> his; void init(int n) { par.resize(n); sz.assign(n, 1); for(int i = 0; i < n; ++i) par[i] = i; his.clear(); } int find(int u) { return par[u] == u ? u : par[u] = find(par[u]); } bool join(int u, int v) { u = find(u); v = find(v); if (u == v) return false; if (sz[u] < sz[v]) swap(u, v); his.emplace_back(0, v, par[v]); his.emplace_back(1, u, sz[u]); par[v] = u; sz[u] += sz[v]; return true; } int snapshot() { return (int)his.size(); } void roll(int tmp) { while ((int)his.size() > tmp) { auto [type, idx, old] = his.back(); his.pop_back(); if (type == 0) par[idx] = old; else sz[idx] = old; } } } dsu; // global buckets (0-based vertex indexing) static vector<int> f[nx], ve[nx], rev[nx]; static map<ii,int> mp; vector<int> simulateCollapse(int n, vector<int> t, vector<int> x, vector<int> y, vector<int> w, vector<int> p) { int c = (int)t.size(); int q = (int)w.size(); // --- normalize input indexing to 0-based for vertices and positions --- // heuristic: if any vertex equals n, assume 1-based and subtract 1 bool vertices_one_based = false; for (int i = 0; i < c; ++i) if (x[i] == n || y[i] == n) { vertices_one_based = true; break; } if (vertices_one_based) { for (int i = 0; i < c; ++i) { x[i]--; y[i]--; } } bool pos_one_based = false; for (int i = 0; i < q; ++i) if (p[i] == n) { pos_one_based = true; break; } if (pos_one_based) for (int i = 0; i < q; ++i) p[i]--; vector<int> del(c, c), ans(q, 0), id(q), out; mp.clear(); for (int i = 0; i < c; ++i) { if (x[i] > y[i]) swap(x[i], y[i]); if (t[i]) { // delete operation: matching add should exist auto it = mp.find({x[i], y[i]}); if (it != mp.end()) del[it->second] = i; else { // unmatched delete: ignore or set to i (defensive) } } else { mp[{x[i], y[i]}] = i; } } iota(id.begin(), id.end(), 0); sort(id.begin(), id.end(), [&](int aa, int bb){ return w[aa] < w[bb]; }); int l = 0, poi = 0; while (l < c) { int r = min(l + bl, c - 1); // clear buckets for (int i = 0; i < n; ++i) { f[i].clear(); ve[i].clear(); rev[i].clear(); } out.clear(); // prepare queries whose w <= r while (poi < q && w[id[poi]] <= r) { if (p[id[poi]] >= 0 && p[id[poi]] < n) f[p[id[poi]]].push_back(id[poi]); else { // defensive: ignore out-of-range p } ++poi; } // classify edges whose add time < l for (int i = 0; i < l; ++i) { if (t[i]) continue; // skip deletes if (del[i] >= l) { if (del[i] > r) { // alive through this block, but removed later -> used in sweep ve[y[i]].push_back(i); rev[x[i]].push_back(i); } else { // deleted within block: treat as exceptional out.push_back(i); } } } // forward sweep int cc = 0; dsu.init(n); for (int i = 0; i < n; ++i) { ++cc; for (int idx : ve[i]) if (dsu.join(x[idx], y[idx])) --cc; for (int idx : f[i]) { int tmp = dsu.snapshot(); int cnt = 0; for (int j : out) if (y[j] <= i && del[j] > w[idx]) { if (dsu.join(x[j], y[j])) { --cc; ++cnt; } } for (int j = l; j <= w[idx]; ++j) { if (t[j] == 0 && y[j] <= i && del[j] > w[idx]) { if (dsu.join(x[j], y[j])) { --cc; ++cnt; } } } ans[idx] += cc; cc += cnt; dsu.roll(tmp); } } // backward sweep cc = 0; dsu.init(n); for (int i = n - 1; i >= 1; --i) { ++cc; for (int idx : rev[i]) if (dsu.join(x[idx], y[idx])) --cc; for (int idx : f[i-1]) { int tmp = dsu.snapshot(); int cnt = 0; for (int j : out) if (x[j] >= i && del[j] > w[idx]) { if (dsu.join(x[j], y[j])) { --cc; ++cnt; } } for (int j = l; j <= w[idx]; ++j) { if (t[j] == 0 && x[j] >= i && del[j] > w[idx]) { if (dsu.join(x[j], y[j])) { --cc; ++cnt; } } } ans[idx] += cc; cc += cnt; dsu.roll(tmp); } } l = r + 1; } return ans; } // Note: main() intentionally omitted (library function)