#include "collapse.h" #include <bits/stdc++.h> #define ii pair<int, int> #define fi first #define se second #define inf 0x3f3f3f3f3f3f3f3f using namespace std; using ll = long long; const ll mod=1e9+7; const int nx=1e5+5; const int bl=300; struct dak { vector<int> par, sz; vector<pair<int&, int>> his; void init(int n) { par.assign(n+1, -1); sz.assign(n+1, 1); his.clear(); } int find(int u) { if(par[u]==-1) return u; return par[u]=find(par[u]); } bool join(int u, int v) { u=find(u); v=find(v); if(u==v) return 0; if(sz[u]<sz[v]) swap(u, v); his.push_back({par[v], par[v]}); his.push_back({sz[u], sz[u]}); par[v]=u; sz[u]+=sz[v]; return 1; } void roll(int tmp) { while(his.size()>tmp) his.back().fi=his.back().se, his.pop_back(); } } dsu; vector<int> simulateCollapse(int n, vector<int> t, vector<int> x, vector<int> y, vector<int> w, vector<int> p) { int c=t.size(), q=w.size(); vector<int> del(c, c), ans(q, 0), id(q), out; vector<vector<int>> f(n), ve(n), rev(n); map<ii, int> mp; mp.clear(); for(int i = 0; i < c; i++) { if(x[i]>y[i]) swap(x[i], y[i]); if(mp.find(ii(x[i], y[i]))!=mp.end()) del[mp[{x[i], y[i]}]]=i; else mp[{x[i], y[i]}]=i; } for(int i = 0; i < q; i++) id[i]=i; sort(id.begin(), id.end(), [&](int aa, int bb) { return w[aa]<w[bb]; }); int l=0, r, poi=0; while(l<=c) { r=min(l+bl, c-1); for(int i = 0; i < n; i++) { f[i].clear(); ve[i].clear(); rev[i].clear(); } out.clear(); while(poi<q && w[id[poi]]<=r) f[p[id[poi]]].emplace_back(id[poi]), poi++; for(int i = 0; i < l; i++) { if(t[i]) continue; if(del[i]>=l) { if(del[i]>r) { ve[y[i]].emplace_back(i); rev[x[i]].emplace_back(i); } else out.emplace_back(i); } } int cc=0; dsu.init(n); for(int i = 0; i < n; i++) { cc++; for(int id:ve[i]) if(dsu.join(x[id], y[id])) cc--; for(int id:f[i]) { int tmp=dsu.his.size(), cnt=0; for(int j:out) if(y[j]<=i && del[j]>w[id]) if(dsu.join(x[j], y[j])) cc--, cnt++; for(int j = l; j <= w[id]; j++) if(t[j]==0 && y[j]<=i && del[j]>w[id]) if(dsu.join(x[j], y[j])) cc--, cnt++; ans[id]+=cc; cc+=cnt; dsu.roll(tmp); } } cc=0; dsu.init(n); for(int i = n-1; i >= 1; i--) { cc++; for(int id:rev[i]) if(dsu.join(x[id], y[id])) cc--; for(int id:f[i-1]) { int tmp=dsu.his.size(), cnt=0; for(int j:out) if(x[j]>=i && del[j]>w[id]) if(dsu.join(x[j], y[j])) cc--, cnt++; for(int j = l; j <= w[id]; j++) if(t[j]==0 && x[j]>=i && del[j]>w[id]) if(dsu.join(x[j], y[j])) cc--, cnt++; ans[id]+=cc; cc+=cnt; dsu.roll(tmp); } } l=r+1; } return ans; } // int main() // { // ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0); // }