#include "collapse.h" #include<bits/stdc++.h> using namespace std; #define foru(i,a,b) for(int i=(a); i<=(b); ++i) #define ford(i,a,b) for(int i=(a); i>=(b); --i) #define rep(i,a) for(int i=0; i<(a); ++i) #define sz(a) (int)(a).size() #define all(a) (a).begin(),(a).end() #define ii pair<int,int> #define vi vector<int> #define vii vector<ii> #define fi first #define se second #define ll long long #define eb emplace_back #define pb push_back const int B=300; const int N=1e5+5; int n,c,q; vi del; map<ii,int> mp; vector<int> ed[N],red[N],que[N],exEd; struct DSU{ int par[N], sz[N]; // safe history: (type, index, old_value) // type 0 -> par[idx] old value // type 1 -> sz[idx] old value vector<tuple<int,int,int>> history; DSU(){ memset(par,0,sizeof(par)); memset(sz,0,sizeof(sz)); history.clear(); } void init(int n){ history.clear(); iota(par, par+n, 0); fill(sz, sz+n, 1); } int find(int x){ return par[x]==x ? x : par[x]=find(par[x]); } bool unite(int x, int y){ x=find(x); y=find(y); if(x==y) return false; if(sz[x]<sz[y]) swap(x,y); history.emplace_back(0, y, par[y]); history.emplace_back(1, x, sz[x]); par[y]=x; sz[x]+=sz[y]; return true; } int snapshot(){ return (int)history.size(); } void rollback(int x){ while((int)history.size()>x){ auto [type, idx, old] = history.back(); history.pop_back(); if(type==0) par[idx]=old; else sz[idx]=old; } } } dsu; vi simulateCollapse(int nn, vi tt, vi xx, vi yy, vi ww, vi pp){ n=nn; c=sz(tt); q=sz(ww); del.assign(c, c); mp.clear(); // Normalize vertex indices to 0-based if they appear 1-based bool one_based_vertices=false; rep(i,c) if(xx[i]==n || yy[i]==n) { one_based_vertices=true; break; } if(one_based_vertices) rep(i,c){ xx[i]--; yy[i]--; } // Normalize pp (positions) to 0-based if needed bool one_based_pos=false; rep(i,q) if(pp[i]==n) { one_based_pos=true; break; } if(one_based_pos) rep(i,q) pp[i]--; rep(i,c){ if(xx[i]>yy[i]) swap(xx[i], yy[i]); if(tt[i]==0){ // add mp[{xx[i], yy[i]}]=i; } else { // delete auto it = mp.find({xx[i], yy[i]}); if(it!=mp.end()) del[it->second]=i; else { // unmatched delete - ignore defensively } } } vi id(q), ans(q,0); iota(all(id), 0); sort(all(id), [&](int a, int b){ return ww[a] < ww[b]; }); int l=0, lq=0; while(l<c){ int r=min(c-1, l+B); // clear buckets rep(i,n){ que[i].clear(); ed[i].clear(); red[i].clear(); } exEd.clear(); // prepare queries whose position p <= r while(lq<q && ww[id[lq]]<=r){ if(pp[id[lq]]>=0 && pp[id[lq]]<n) que[pp[id[lq]]].eb(id[lq]); ++lq; } // prepare edges added before block rep(i,l) if(tt[i]==0){ if(del[i]>=l){ if(del[i]>r){ ed[yy[i]].eb(i); red[xx[i]].eb(i); } else { exEd.eb(i); } } } // forward sweep int cc=0; dsu.init(n); rep(i,n){ ++cc; for(int j: ed[i]) if(dsu.unite(xx[j], yy[j])) --cc; for(int j: que[i]){ int tmp = dsu.snapshot(); int cnt = 0; rep(k, (int)exEd.size()){ int ide = exEd[k]; if(yy[ide] <= i && del[ide] > ww[j]){ if(dsu.unite(xx[ide], yy[ide])) { --cc; ++cnt; } } } foru(k, l, ww[j]){ if(tt[k]==0 && yy[k] <= i && del[k] > ww[j]){ if(dsu.unite(xx[k], yy[k])) { --cc; ++cnt; } } } ans[j] += cc; cc += cnt; dsu.rollback(tmp); } } // backward sweep cc = 0; dsu.init(n); ford(i, n-1, 1){ ++cc; for(int j: red[i]) if(dsu.unite(xx[j], yy[j])) --cc; for(int j: que[i-1]){ int tmp = dsu.snapshot(); int cnt = 0; rep(k, (int)exEd.size()){ int ide = exEd[k]; if(xx[ide] >= i && del[ide] > ww[j]){ if(dsu.unite(xx[ide], yy[ide])) { --cc; ++cnt; } } } foru(k, l, ww[j]){ if(tt[k]==0 && xx[k] >= i && del[k] > ww[j]){ if(dsu.unite(xx[k], yy[k])) { --cc; ++cnt; } } } ans[j] += cc; cc += cnt; dsu.rollback(tmp); } } l = r + 1; } return ans; }