#include "collapse.h"
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
const ll N=1e5+29;
ll n,pr[N],sz[N],mx[N],mn[N],cnt,st[4*N],z[4*N];
vector<int>w;
bool cmp(ll a,ll b){
return w[a]<w[b];
}ll get(ll x){
return (pr[x]==x ? x : pr[x]=get(pr[x]));
}void push(ll v,ll l,ll r){
ll mid=(r+l)>>1;
st[v*2]+=(mid-l+1)*z[v];
st[v*2+1]+=(r-mid)*z[v];
z[v*2]+=z[v];
z[v*2+1]+=z[v];
z[v]=0;
}void upd(ll v,ll l,ll r,ll x,ll y,ll value){
if(l>y||x>r)return;
if(x<=l&&r<=y){
st[v]+=value*(r-l+1);
z[v]+=value;
return;
}
push(v,l,r);
ll mid=(r+l)/2;
upd(v*2,l,mid,x,y,value);
upd(v*2+1,mid+1,r,x,y,value);
st[v]=st[v*2]+st[v*2+1];
return;
}
ll get(ll v,ll l,ll r,ll x,ll y){
if(l>y||x>r) {
return 0;
}
if(x<=l&&r<=y){
return st[v];
}
push(v,l,r);
ll mid=(r+l)/2;
return get(v*2,l,mid,x,y)+get(v*2+1,mid+1,r,x,y);
}
void upd(ll i,ll x){
ll l=mn[i];
ll r=mx[i]-1;
if(l>r)return;
upd(1,1,n,l,r,x);
}
void uni(ll v,ll u){
u=get(u);
v=get(v);
if(u==v)return;
if(sz[v]<sz[u])swap(v,u);
upd(v,-1);
upd(u,-1);
pr[u]=v;
mx[v]=max(mx[v],mx[u]);
mn[v]=min(mn[v],mn[u]);
upd(v,1);
cnt--;
sz[v]+=sz[u];
}
vector<int> simulateCollapse(int n,vector<int> T,vector<int> X,vector<int> Y,vector<int> W,vector<int> P) {
vector<int>ans(W.size());
w=W;
vector<ll>A(W.size());
iota(A.begin(),A.end(),0);
sort(A.begin(),A.end(),&cmp);
ll j=-1;
for(ll i=0;i<n;i++){
pr[i]=i;
sz[i]=1;
mx[i]=mn[i]=i;
}cnt=n;
for(ll i:A){
while(j<W[i]){
j++;
uni(X[j],Y[j]);
}
ans[i]=get(1,1,n,P[i],P[i]);
}
return ans;
}
