#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 bit(s,i) (((s)>>(i))&1) #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 #define __builtin_popcount __builtin_popcountll #define _ << " " << template <class X, class Y> bool maxi(X &x, Y y){return x<y?x=y,true:false;} template <class X, class Y> bool mini(X &x, Y y){return x>y?x=y,true:false;} 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]; vector<pair<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 : 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.eb(par[y],par[y]); history.eb(sz[x],sz[x]); par[y]=x; sz[x]+=sz[y]; return true; } int snapshot(){ return sz(history); } void rollback(int x){ while(sz(history)>x){ history.back().fi=history.back().se; history.pop_back(); } } } dsu; vi simulateCollapse(int nn, vi tt, vi xx, vi yy, vi ww, vi pp){ n=nn, c=sz(tt), q=sz(ww); del.resize(c,c); 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{ del[mp[{xx[i],yy[i]}]]=i; } } vi id(q),ans(q,0); iota(all(id),0); sort(all(id),[&](int x, int y){return ww[x]<ww[y];}); int l=0, lq=0; while(l<c){ int r=min(c-1,l+B); /// reset rep(i,n){ que[i].clear(); ed[i].clear(); red[i].clear(); } exEd.clear(); /// prepare for queries while(lq<q && ww[id[lq]]<=r){ que[pp[id[lq]]].eb(id[lq]); ++lq; } /// prepare for adding edges 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); } } } /// sweep line for answer queries offline 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(), cnt=0; rep(k,sz(exEd)){ 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); } } 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(), cnt=0; rep(k,sz(exEd)){ 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; }