#include "collapse.h"
#include<bits/stdc++.h>
using namespace std;
int n;
struct DSU
{
int father[100005],siz[100005];
vector<pair<pair<int,int>,int>> history;
void init()
{
history.clear();
for(int i=0;i<n;i++)
father[i]=i, siz[i]=1;
}
int gas(int x)
{
if(father[x]!=x)
return gas(father[x]);
return x;
}
void unite(int x, int y)
{
x = gas(x);
y = gas(y);
if(x==y)
return;
if(siz[x]<siz[y])
swap(x,y);
history.push_back({{y,father[y]},0});
history.push_back({{x,siz[x]},1});
father[y] = x;
siz[x] += siz[y];
}
int get_time()
{
return history.size();
}
void rollback(int t)
{
while((int)history.size() > t)
{
if(history.back().second == 0)
father[history.back().first.first] = history.back().first.second;
else
siz[history.back().first.first] = history.back().first.second;
history.pop_back();
}
}
};
vector<pair<int,int>> begin_on_t[100005],end_on_t[100005];
vector<pair<int,pair<int,int>>> begin_on_poz[100005],end_on_poz[100005];
void add_edge(int tle, int tri, int x, int y)
{
assert(tle<=tri);
assert(x<=y);
begin_on_t[tle].push_back({x,y});
end_on_t[tri].push_back({x,y});
begin_on_poz[x].push_back({y,{tle,tri}});
end_on_poz[y].push_back({x,{tle,tri}});
}
vector<pair<pair<int,int>,int>> qrys;
const int BUC = 350;
bool cmp_mo(pair<pair<int,int>,int> x, pair<pair<int,int>,int> y)
{
swap(x.first.first, x.first.second);
swap(y.first.first, y.first.second);
if(x.first.first/BUC != y.first.first/BUC)
return x.first.first/BUC < y.first.first/BUC;
if((x.first.first/BUC)%2==0)
return x.first.second < y.first.second;
else
return x.first.second > y.first.second;
}
vector<pair<int,int>> on_node[400005];
int who[100005];
void upd(int nod, int st, int dr, int le, int ri, int x, int y)
{
if(le>ri)
return;
if(le==st && dr==ri)
{
on_node[nod].push_back({x,y});
return;
}
int mij=(st+dr)/2;
upd(nod*2,st,mij,le,min(mij,ri),x,y);
upd(nod*2+1,mij+1,dr,max(mij+1,le),ri,x,y);
}
vector<int> sol;
DSU dsu;
void dfs_dynamic(int nod, int st, int dr)
{
int old_t = dsu.get_time();
for(auto [x,y]:on_node[nod])
dsu.unite(x,y);
if(st==dr)
{
sol[who[st]] = n - dsu.get_time()/2;
}
else
{
int mij=(st+dr)/2;
dfs_dynamic(nod*2,st,mij);
dfs_dynamic(nod*2+1,mij+1,dr);
}
dsu.rollback(old_t);
}
void add_dynamic_edge(int tle, int tri, int x, int y)
{
if(tle>tri)
return;
upd(1,1,qrys.size(),tle,tri,x,y);
}
map<pair<int,int>,int> dynamic_time;
void baga_dynamic(int t, int x, int y)
{
if(x>y)
swap(x,y);
dynamic_time[{x,y}] = t;
}
void scoate_dynamic(int t, int x, int y)
{
if(x>y)
swap(x,y);
if(dynamic_time[{x,y}])
{
add_dynamic_edge(dynamic_time[{x,y}],t-1,x,y);
dynamic_time[{x,y}] = 0;
}
}
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;
map<pair<int,int>,int> construction_day;
for(int i=0;i<T.size();i++)
{
if(X[i] > Y[i])
swap(X[i],Y[i]);
if(T[i]==0)
{
construction_day[{X[i],Y[i]}] = i;
}
else
{
add_edge(construction_day[{X[i],Y[i]}],i-1,X[i],Y[i]);
construction_day[{X[i],Y[i]}] = -1;
}
}
for(auto it:construction_day)
{
if(it.second != -1)
{
add_edge(it.second, (int)T.size() + 2, it.first.first, it.first.second);
}
}
for(int i=0;i<W.size();i++)
{
qrys.push_back({{W[i],P[i]},i});
}
sort(qrys.begin(),qrys.end(),cmp_mo);
int myt = -1, myp = qrys[0].first.second;
for(int i=1;i<=qrys.size();i++)
{
int w = qrys[i-1].first.first, p = qrys[i-1].first.second, id = qrys[i-1].second;
who[i] = id;
while(myt < w)
{
if(myt!=-1)
for(auto [x,y]:end_on_t[myt])
scoate_dynamic(i,x,y);
myt++;
for(auto [x,y]:begin_on_t[myt])
if(y <= p || x > p)
baga_dynamic(i,x,y);
}
while(myt > w)
{
for(auto [x,y]:begin_on_t[myt])
scoate_dynamic(i,x,y);
myt--;
for(auto [x,y]:end_on_t[myt])
if(y <= p || x > p)
baga_dynamic(i,x,y);
}
while(myp < p)
{
myp++;
for(auto [other_poz,t]:end_on_poz[myp])
if(t.first <= w && w <= t.second)
baga_dynamic(i,other_poz,myp);
for(auto [other_poz,t]:begin_on_poz[myp])
scoate_dynamic(i,myp,other_poz);
}
while(myp > p)
{
for(auto [other_poz,t]:end_on_poz[myp])
scoate_dynamic(i,other_poz,myp);
for(auto [other_poz,t]:begin_on_poz[myp])
if(t.first <= w && w <= t.second)
baga_dynamic(i,myp,other_poz);
myp--;
}
}
for(auto it:dynamic_time)
if(it.second != 0)
scoate_dynamic((int)qrys.size() + 1, it.first.first, it.first.second);
sol.resize(W.size());
dsu.init();
dfs_dynamic(1,1,qrys.size());
return sol;
}
