#include "collapse.h"
#include <bits/stdc++.h>
using namespace std;
static const int MAXN = 100000;
typedef pair<int,int> pii;
int a, b, c;
vector<int> t, z, z1, w, w1;
vector<int> res;
struct Interval { int u, v, l, r; };
vector<Interval> intervals;
vector<vector<pii>> pos;
vector<vector<pii>> seg_pref, seg_suf;
struct ST {
int n;
vector<int> f, lazy;
void init(int _n) {
n = _n;
f.assign(4*n+4, 0);
lazy.assign(4*n+4, 0);
}
void apply(int id, int l, int r, int v) {
f[id] += v;
lazy[id] += v;
}
void push(int id) {
if (!lazy[id]) return;
apply(id*2, 0, 0, lazy[id]);
apply(id*2+1, 0, 0, lazy[id]);
lazy[id] = 0;
}
void update(int id, int l, int r, int L, int R, int v) {
if (R < l || r < L) return;
if (L <= l && r <= R) {
apply(id, l, r, v);
return;
}
int mid = (l+r)>>1;
push(id);
update(id*2, l, mid, L, R, v);
update(id*2+1, mid+1, r, L, R, v);
f[id] = f[id*2] + f[id*2+1];
}
int get(int id, int l, int r, int p) {
if (l == r) return f[id];
int mid = (l+r)>>1;
push(id);
return p <= mid ? get(id*2, l, mid, p) : get(id*2+1, mid+1, r, p);
}
};
ST stree;
void add_interval(vector<vector<pii>>& seg, int id, int l, int r, int L, int R, pii e) {
if (R < l || r < L) return;
if (L <= l && r <= R) {
seg[id].push_back(e);
return;
}
int mid = (l+r)>>1;
add_interval(seg, id*2, l, mid, L, R, e);
add_interval(seg, id*2+1, mid+1, r, L, R, e);
}
int par[MAXN+5], sz[MAXN+5];
struct Roll { int y, sy, id, type, w; };
vector<Roll> roll_stack;
int findp(int u) { return par[u]==u ? u : findp(par[u]); }
bool join(int u, int v, int id, int type) {
int x = findp(u), y = findp(v);
if (x == y) return false;
if (sz[x] < sz[y]) swap(x,y);
roll_stack.push_back({y, sz[y], id, type, (type==1? max(u,v): min(u,v))});
par[y] = x;
sz[x] += sz[y];
return true;
}
void rollback(int id) {
while (!roll_stack.empty() && roll_stack.back().id == id) {
auto R = roll_stack.back();
roll_stack.pop_back();
int y = R.y, sy = R.sy;
int type = R.type, w = R.w;
int x = par[y];
sz[x] -= sy;
par[y] = y;
// undo segment-tree update
if (type == 1) {
stree.update(1, 0, a-1, w, a-1, +1);
} else {
stree.update(1, 0, a-1, 0, w, +1);
}
}
}
void dfs_pref(int id, int l, int r) {
sort(seg_pref[id].begin(), seg_pref[id].end(), [](pii A, pii B){ return max(A.first,A.second) < max(B.first,B.second); });
for (auto &e : seg_pref[id]) {
if (join(e.first, e.second, id, 1)) {
int wv = max(e.first, e.second);
stree.update(1, 0, a-1, wv, a-1, -1);
}
}
if (l == r) {
for (auto &pr : pos[l]) res[pr.second] = stree.get(1,0,a-1,pr.first);
} else {
int m=(l+r)>>1;
dfs_pref(id*2, l, m);
dfs_pref(id*2+1, m+1, r);
}
rollback(id);
}
void dfs_suf(int id, int l, int r) {
sort(seg_suf[id].begin(), seg_suf[id].end(), [](pii A, pii B){ return min(A.first,A.second) > min(B.first,B.second); });
for (auto &e : seg_suf[id]) {
if (join(e.first, e.second, id, 2)) {
int wv = min(e.first, e.second);
stree.update(1, 0, a-1, 0, wv, -1);
}
}
if (l == r) {
for (auto &pr : pos[l]) res[pr.second] += stree.get(1,0,a-1,pr.first);
} else {
int m=(l+r)>>1;
dfs_suf(id*2, l, m);
dfs_suf(id*2+1, m+1, r);
}
rollback(id);
}
vector<int> simulateCollapse(int N, vector<int> T_, vector<int> X_, vector<int> Y_, vector<int> W_, vector<int> P_) {
a=N; b=T_.size(); c=W_.size();
t=T_; z=X_; z1=Y_; w=W_; w1=P_;
res.assign(c,0);
pos.assign(b,{});
seg_pref.assign(4*b+4,{});
seg_suf.assign(4*b+4,{});
map<pii,int> last;
for (int i=0;i<b;i++) {
pii e={z[i],z1[i]};
if (t[i]==0) last[e]=i;
else { intervals.push_back({e.first,e.second,last[e],i-1}); last.erase(e); }
}
for (auto &p:last) intervals.push_back({p.first.first,p.first.second,p.second,b-1});
for (auto &I: intervals) {
add_interval(seg_pref,1,0,b-1,I.l,I.r,{I.u,I.v});
add_interval(seg_suf,1,0,b-1,I.l,I.r,{I.u,I.v});
}
for (int i=0;i<c;i++) pos[w1[i]].push_back({w[i],i});
stree.init(a);
for (int x=0;x<a;x++) stree.update(1,0,a-1,x,a-1,1);
iota(par,par+a,0);
fill(sz,sz+a,1);
dfs_pref(1,0,b-1);
stree.init(a);
for (int x=0;x<a;x++) stree.update(1,0,a-1,0,x,1);
iota(par,par+a,0);
fill(sz,sz+a,1);
dfs_suf(1,0,b-1);
return res;
}
