#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; const int BLOCK = 500; 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]++; } } }; ll n; bool cmpa1( const pair<pair<ll,ll>,ll> &a, const pair<pair<ll,ll>,ll> &b){ if(a.fst.snd < b.fst.snd) return true; else if(a.fst.snd > b.fst.snd) return false; else if( a.fst.fst<b.fst.fst) return true; else if( a.fst.fst>b.fst.fst) return false; return a.snd<b.snd; } ll res[5000000]; // en ari tienen que estar activos o que aparecen en ord void solve(vector<pair<ll,ll>> ari, vector<pair<pair<ll,ll>,pair<ll,ll>>> ord, vector<pair<pair<ll,ll>,ll>> qu){ bool fij[SZ(ari)]; forn(i,0,SZ(ari)) fij[i]=true; forn(i,0,SZ(ord)){ fij[ lower_bound(ALL(ari), ord[i].snd )-ari.begin() ]=false; } vector<pair<ll,ll>> lari; // ari sorted by left node lari.pb({-1000,0}); forn(i,0,SZ(ari)) if(fij[i]) lari.pb(ari[i]); vector<pair<ll,ll>> rari; // ari sorted by right node forn(i,0,SZ(ari)) if(fij[i]) rari.pb({ari[i].snd,ari[i].fst}); sort(ALL(rari)); rari.pb({1000000000,0}); ll cnt = 0; ll cmp1[SZ(rari)]; // desde 0 hasta i UnionFind uf1(n); ll k = 0; sort(ALL(qu)); forn(i,0,SZ(rari)){ while(k<SZ(qu) && qu[k].fst.snd<rari[i].fst){ UnionFind tmp(n); ll rcnt = 0; vector<ll> ract(SZ(ari),false); forn(h,0,SZ(ord)) if(ord[h].snd.snd<=qu[k].fst.snd && ord[h].fst.fst<=qu[k].fst.fst){ //cout<<ord[h].snd.fst<<" "<<ord[h].snd.snd<<'\n'; if(ract[lower_bound(ALL(ari), ord[h].snd )-ari.begin() ]) ract[lower_bound(ALL(ari), ord[h].snd )-ari.begin() ]=false; else ract[lower_bound(ALL(ari), ord[h].snd )-ari.begin() ]=true; } forn(h,0,SZ(ract)) if(ract[h]){ //cout<<ari[h].fst<<" "<<ari[h].snd<<" se puede usar\n"; if(tmp.Find(uf1.Find(ari[h].fst))!=tmp.Find(uf1.Find(ari[h].snd))){ tmp.Union(uf1.Find(ari[h].fst), uf1.Find(ari[h].snd)); rcnt++; } } ll rres = (i-1>=0?cmp1[i-1]:0) - rcnt + qu[k].fst.snd+1 - (i-1>=0?rari[i-1].fst+1:0); //cout<<qu[k].fst.fst<<" "<<qu[k].fst.snd<<" left "<<(i-1>=0?cmp1[i-1]:0)<<" - "<< rcnt<<" + "<< qu[k].fst.snd+1 <<" - "<< (i-1>=0?rari[i-1].fst+1:0)<<'\n'; res[qu[k].snd]=rres; k++; } if(rari[i].fst==1000000000) break; if(uf1.Find(rari[i].fst)!=uf1.Find(rari[i].snd)){ cnt++; uf1.Union(rari[i].fst,rari[i].snd); } cmp1[i]= rari[i].fst+1 - cnt; } // cout<<"--------------------\n"; sort(ALL(qu),cmpa1); k=0; cnt = 0; ll cmp2[SZ(lari)]; // desde n hasta i UnionFind uf2(n); for(int i = SZ(lari)-1; i>=0; i--){ while(k<SZ(qu) && qu[k].fst.snd+1>lari[i].fst){ UnionFind tmp(n); ll rcnt = 0; vector<ll> ract(SZ(ari),0); forn(h,0,SZ(ord)) if(ord[h].snd.fst>=qu[k].fst.snd+1 && ord[h].fst.fst<=qu[k].fst.fst){ //cout<<ord[h].snd.fst<<" "<<ord[h].snd.snd<<'\n'; if(ract[ lower_bound(ALL(ari), ord[h].snd) - ari.begin() ]) ract[ lower_bound(ALL(ari) , ord[h].snd) - ari.begin()]=false; else ract[ lower_bound(ALL(ari), ord[h].snd)- ari.begin()] = true; } forn(h,0,SZ(ari)) if(ract[h]){// cout<<" se puede usar "<<ari[h].fst<<" "<<ari[h].snd<<'\n'; if(tmp.Find(uf2.Find(ari[h].fst))!=tmp.Find(uf2.Find(ari[h].snd))){ tmp.Union(uf2.Find(ari[h].fst),uf2.Find(ari[h].snd)); rcnt++; } } ll rres = (i+1<SZ(lari)?cmp2[i+1]:0) -rcnt + (n-(qu[k].fst.snd+1)) - (i+1<SZ(lari)?n-(lari[i+1].fst+1):0); //cout<<qu[k].fst.fst<<" "<<qu[k].fst.snd<<" right "<<(i+1<SZ(lari)?cmp2[i+1]:0)<<" - "<<rcnt<<" + "<<(n-(qu[k].fst.snd+1))<<" - "<< (i+1<SZ(lari)?n-(lari[i+1].fst+1):0)<<'\n'; res[qu[k].snd]+=rres; k++; } if(lari[i].fst<0) break; if(uf2.Find(lari[i].fst)!=uf2.Find(lari[i].snd)){ cnt++; uf2.Union(lari[i].fst,lari[i].snd); } cmp2[i]=(n-lari[i].fst) - cnt; } } 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) { n=N; 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<bool> mod(SZ(ari),false); vector<pair<pair<ll,ll>,pair<ll,ll>>> ord; forn(i,0,SZ(T)) ord.pb({{i,T[i]},{min(X[i],Y[i]),max(X[i],Y[i])}}); vector<pair<pair<ll,ll>,ll>> qu; forn(i,0,SZ(W)) qu.pb({{W[i],P[i]},i}); sort(ALL(qu)); ll iord = 0; ll iqu = 0; vector<pair<pair<ll,ll>,ll>> nqu; vector<pair<pair<ll,ll>,pair<ll,ll>>> nord; vector<pair<ll,ll>> nari; ll ltime = 0; ll ntime = BLOCK; do{ while(iqu<SZ(qu) && qu[iqu].fst.fst>=ltime && qu[iqu].fst.fst<=ntime){ nqu.pb(qu[iqu]); iqu++; } while(iord<SZ(ord) && ord[iord].fst.fst>=ltime && ord[iord].fst.fst <=ntime){ if(ord[iord].fst.snd==0) act[ lower_bound( ALL(ari), ord[iord].snd) - ari.begin()]=true; else act[ lower_bound( ALL(ari), ord[iord].snd) - ari.begin()]=false; nord.pb(ord[iord]); nari.pb(ord[iord].snd); iord++; } forn(i,0,SZ(act)) if(act[i]) nari.pb(ari[i]); sort(ALL(nari)); nari.erase(unique(ALL(nari)),nari.end()); solve(nari,nord,nqu); ltime=ntime+1; ntime=ltime+BLOCK; }while(ltime<SZ(T)+10); vector<int> rres(SZ(W)); forn(i,0,SZ(W)) rres[i]=res[i]; return rres; }