#include "collapse.h"
#include <bits/stdc++.h>
#define ii pair<int, int>
#define fi first
#define se second
#define inf 0x3f3f3f3f3f3f3f3f
using namespace std;
using ll = long long;
const ll mod=1e9+7;
const int nx=1e5+5;
const int bl=300;
struct dak
{
vector<int> par, sz;
vector<pair<int&, int>> his;
void init(int n)
{
par.assign(nx, -1);
sz.assign(nx, 1);
his.clear();
}
int find(int u)
{
if(par[u]==-1) return u;
return par[u]=find(par[u]);
}
bool join(int u, int v)
{
u=find(u);
v=find(v);
if(u==v) return 0;
if(sz[u]<sz[v]) swap(u, v);
his.push_back({par[v], par[v]});
his.push_back({sz[u], sz[u]});
par[v]=u;
sz[u]+=sz[v];
return 1;
}
void roll(int tmp)
{
while(his.size()>tmp)
his.back().fi=his.back().se, his.pop_back();
}
} dsu;
vector<int> simulateCollapse(int n, vector<int> t, vector<int> x, vector<int> y, vector<int> w, vector<int> p)
{
int c=t.size(), q=w.size();
vector<int> del(nx, c), ans(q, 0), id(q), out;
vector<vector<int>> f(nx), ve(nx), rev(nx);
map<ii, int> mp;
mp.clear();
for(int i = 0; i < c; i++)
{
if(x[i]>y[i]) swap(x[i], y[i]);
if(t[i]) del[mp[{x[i], y[i]}]]=i;
else mp[{x[i], y[i]}]=i;
}
for(int i = 0; i < q; i++)
id[i]=i;
sort(id.begin(), id.end(), [&](int aa, int bb)
{
return w[aa]<w[bb];
});
int l=0, r, poi=0;
while(l<c)
{
r=min(l+bl, c-1);
for(int i = 0; i < n; i++)
{
f[i].clear();
ve[i].clear();
rev[i].clear();
}
out.clear();
while(poi<q && w[id[poi]]<=r)
f[p[id[poi]]].emplace_back(id[poi]), poi++;
for(int i = 0; i < l; i++)
{
if(t[i]) continue;
if(del[i]>=l)
{
if(del[i]>r)
{
ve[y[i]].emplace_back(i);
rev[x[i]].emplace_back(i);
}
else out.emplace_back(i);
}
}
int cc=0;
dsu.init(n);
for(int i = 0; i < n; i++)
{
cc++;
for(int id:ve[i])
if(dsu.join(x[id], y[id]))
cc--;
for(int id:f[i])
{
int tmp=dsu.his.size(), cnt=0;
for(int j:out)
if(y[j]<=i && del[j]>w[id])
if(dsu.join(x[j], y[j]))
cc--, cnt++;
for(int j = l; j <= w[id]; j++)
if(t[j]==0 && y[j]<=i && del[j]>w[id])
if(dsu.join(x[j], y[j]))
cc--, cnt++;
ans[id]+=cc;
cc+=cnt;
dsu.roll(tmp);
}
}
cc=0;
dsu.init(n);
for(int i = n-1; i >= 1; i--)
{
cc++;
for(int id:rev[i])
if(dsu.join(x[id], y[id]))
cc--;
for(int id:f[i-1])
{
int tmp=dsu.his.size(), cnt=0;
for(int j:out)
if(x[j]>=i && del[j]>w[id])
if(dsu.join(x[j], y[j]))
cc--, cnt++;
for(int j = l; j <= w[id]; j++)
if(t[j]==0 && x[j]>=i && del[j]>w[id])
if(dsu.join(x[j], y[j]))
cc--, cnt++;
ans[id]+=cc;
cc+=cnt;
dsu.roll(tmp);
}
}
l=r+1;
}
return ans;
}
// int main()
// {
// ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
// }
