#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); #define DEBUG 0 // Cambia a 0 para desactivar #if DEBUG #define debug(x) cout << x #else #define debug(x) #endif 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; } bool cmpa( 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),cmpa); forn(i,0,SZ(rari)){ debug("Rari "<<i<<" "<<rari[i].fst<<" "<<rari[i].snd<<'\n'); while(k<SZ(qu) && qu[k].fst.snd<rari[i].fst){ UnionFind tmp(n); ll rcnt = 0; vector<ll> ract(SZ(ari),false); vector<ll> first(SZ(ari),-1); forn(h,0,SZ(ord)) if(ord[h].snd.snd<=qu[k].fst.snd &&first[lower_bound(ALL(ari), ord[h].snd )-ari.begin()]==-1){ first[lower_bound(ALL(ari), ord[h].snd )-ari.begin()]=0; if(ord[h].fst.snd==1){ ract[lower_bound(ALL(ari), ord[h].snd )-ari.begin()]=true; } } forn(h,0,SZ(ord)) if(ord[h].snd.snd<=qu[k].fst.snd && ord[h].fst.fst<=qu[k].fst.fst){ debug(ord[h].snd.fst<<" "<<ord[h].snd.snd<<'\n'); if(ord[h].fst.snd==1) 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]){ debug(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); debug(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; } debug("--------------------\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--){ debug("Lari "<<i<<" "<<lari[i].fst<<" "<<lari[i].snd<<'\n'); while(k<SZ(qu) && qu[k].fst.snd+1>lari[i].fst){ UnionFind tmp(n); ll rcnt = 0; vector<ll> ract(SZ(ari),0); vector<ll> first(SZ(ari),-1); forn(h,0,SZ(ord)) if(ord[h].snd.fst>=qu[k].fst.snd+1 &&first[lower_bound(ALL(ari), ord[h].snd )-ari.begin()]==-1){ first[lower_bound(ALL(ari), ord[h].snd )-ari.begin()]=0; if(ord[h].fst.snd==1){ ract[lower_bound(ALL(ari), ord[h].snd )-ari.begin()]=true; } } forn(h,0,SZ(ord)) if(ord[h].snd.fst>=qu[k].fst.snd+1 && ord[h].fst.fst<=qu[k].fst.fst){ debug(ord[h].snd.fst<<" "<<ord[h].snd.snd<<'\n'); if(ord[h].fst.snd) 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]){ debug(" 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):0); debug(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):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{ nari.clear(); nqu.clear(); nord.clear(); while((iqu<SZ(qu) || iord<SZ(ord) ) && SZ(nqu)+SZ(nord)<=BLOCK){ if(iqu>=SZ(qu) || (iord<SZ(ord) && qu[iqu].fst.fst >= ord[iord].fst.fst)){ 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++; }else{ nqu.pb(qu[iqu]); iqu++; } } forn(i,0,SZ(act)) if(act[i]) nari.pb(ari[i]); sort(ALL(nari)); nari.erase(unique(ALL(nari)),nari.end()); debug("Nueva llamada "); for(auto nind:nari) debug(nind.fst<<" "<<nind.snd<<" - "); debug('\n'); debug("iqu "<<iqu<<" iord"<<iord<<'\n'); solve(nari,nord,nqu); }while(SZ(nord)>0 || SZ(nqu)>0); vector<int> rres(SZ(W)); forn(i,0,SZ(W)) rres[i]=res[i]; return rres; }