#include "collapse.h"
#include<bits/stdc++.h>
using namespace std;
int n;
const int BUC = 320;
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;
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];
vector<pair<pair<int,int>,pair<int,int>>> edges;
void add_edge(int tle, int tri, int x, int y)
{
assert(tle<=tri);
assert(x<=y);
edges.push_back({{tle,tri},{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[100005];
bool cmp_edge(pair<pair<int,int>,pair<int,int>> x, pair<pair<int,int>,pair<int,int>> y)
{
return x.second.second < y.second.second;
}
bool cmp_edge2(pair<pair<int,int>,pair<int,int>> x, pair<pair<int,int>,pair<int,int>> y)
{
return x.second.first > y.second.first;
}
bool cmp_qry(pair<pair<int,int>,int> x, pair<pair<int,int>,int> y)
{
return x.first.second < y.first.second;
}
bool cmp_qry2(pair<pair<int,int>,int> x, pair<pair<int,int>,int> y)
{
return x.first.first > x.first.first;
}
vector<int> sol;
void solve(int maxb)
{
sort(edges.begin(),edges.end(),cmp_edge);
for(int b=0;b<=maxb;b++)
{
DSU dsu;
dsu.init();
int ble = b*BUC, bri = (b+1)*BUC - 1;
sort(qrys[b].begin(),qrys[b].end(),cmp_qry);
vector<pair<pair<int,int>,pair<int,int>>> base_edges,special_edges;
for(auto [t,e]:edges)
{
if(t.first <= ble && bri <= t.second)
base_edges.push_back({t,e});
else
special_edges.push_back({t,e});
}
int poz_base=0;
for(auto [q,id]:qrys[b])
{
int w = q.first, p = q.second;
while(poz_base < base_edges.size() && base_edges[poz_base].second.second <= p)
{
dsu.unite(base_edges[poz_base].second.first, base_edges[poz_base].second.second);
poz_base++;
}
int old_t = dsu.get_time();
for(auto [t,e]:special_edges)
if(t.first <= w && w <= t.second && e.second <= p)
dsu.unite(e.first, e.second);
sol[id] += dsu.get_time()/2;
dsu.rollback(old_t);
}
}
sort(edges.begin(),edges.end(),cmp_edge2);///------------------------------------
for(int b=0;b<=maxb;b++)
{
DSU dsu;
dsu.init();
int ble = b*BUC, bri = (b+1)*BUC - 1;
sort(qrys[b].begin(),qrys[b].end(),cmp_qry2);
vector<pair<pair<int,int>,pair<int,int>>> base_edges,special_edges;
for(auto [t,e]:edges)
{
if(t.first <= ble && bri <= t.second)
base_edges.push_back({t,e});
else
special_edges.push_back({t,e});
}
int poz_base=0;
for(auto [q,id]:qrys[b])
{
int w = q.first, p = q.second;
while(poz_base < base_edges.size() && base_edges[poz_base].second.second > p)
{
dsu.unite(base_edges[poz_base].second.first, base_edges[poz_base].second.second);
poz_base++;
}
int old_t = dsu.get_time();
for(auto [t,e]:special_edges)
if(t.first <= w && w <= t.second && e.second > p)
dsu.unite(e.first, e.second);
sol[id] += dsu.get_time()/2;
dsu.rollback(old_t);
}
}
}
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[W[i]/BUC].push_back({{W[i],P[i]},i});
sol.resize((int)W.size(),0);
solve(T.size()/BUC);
for(int i=0;i<W.size();i++)
sol[i] = n - sol[i];
return sol;
}
