#include "collapse.h" #include <bits/stdc++.h> #define fst first #define snd second #define pb push_back #define forn(i,a,b) for(int i = a; i<b; i++) #define SZ(x) (int)x.size() #define ALL(x) x.begin(),x.end() #define mset(a,v) memset(a,v,sizeof(a)) #define FIN ios::sync_with_stdio(0); cin.tie(0); cout.tie(0); using namespace std; typedef long long ll; struct UnionFind{ ll n; vector<ll> p; vector<ll> sz; UnionFind(ll n=0):n(n),p(n,0),sz(n,1){ forn(i,0,n) p[i]=i; } ll Find(ll x){ return (p[x]==x?x:Find(p[x])); } void Union(ll a,ll b){ ll pa = Find(a); ll pb = Find(b); if(pa==pb) return; if(sz[pa]<sz[pb]){ p[pa]=pb; }else{ p[pb]=pa; if(sz[pa]==sz[pb]) sz[pa]++; } } }; 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) { vector<pair<ll,ll>> ari; forn(i,0,SZ(X)) ari.pb({min(X[i],Y[i]),max(X[i],Y[i])}); sort(ALL(ari)); ari.erase(unique(ALL(ari)),ari.end()); vector<bool> act(SZ(ari),false); vector<pair<pair<ll,ll>,ll>> qu; forn(i,0,SZ(W)) qu.pb({{W[i],P[i]},i}); sort(ALL(qu)); vector<int> res(SZ(qu)); ll j = 0; forn(i,0,SZ(qu)){ //cout<<"para la querie "<<qu[i].fst.fst<<" "<<qu[i].fst.snd<<'\n'; UnionFind uf(N); while(j<=qu[i].fst.fst){ ll ind = lower_bound(ALL(ari),(pair<ll,ll>){min(X[j],Y[j]),max(X[j],Y[j])})-ari.begin(); //cout<<ind<<'\n'; if(act[ind]) act[ind]=false; else act[ind]=true; j++; } ll cnt = N; forn(h,0,SZ(act)){ if(act[h] && (ari[h].snd<=qu[i].fst.snd || ari[h].fst>=qu[i].fst.snd+1)){ //cout<<ari[h].fst<<" "<<ari[h].snd<<'\n'; if(uf.Find(ari[h].fst)!=uf.Find(ari[h].snd)){ cnt--; uf.Union(ari[h].fst,ari[h].snd); } } } res[qu[i].snd]=cnt; } return res; }