#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;
map<pii,int> m;
struct Edge { int x, y, l, r; };
vector<Edge> vec;
vector<vector<pii>> pos;
vector<vector<pii>> seg_pref, seg_suf;
struct ST {
int n;
vector<int> f, lazy;
ST(int _n=0) { init(_n); }
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]) {
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 f1;
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];
stack<pair<pii,int>> st;
int findp(int u) { return par[u]==u ? u : findp(par[u]); }
bool join(int x, int y, int id) {
x = findp(x); y = findp(y);
if (x == y) return false;
if (sz[x] < sz[y]) swap(x,y);
st.push({{y, sz[y]}, id});
par[y] = x;
sz[x] += sz[y];
return true;
}
void rollback(int id) {
while (!st.empty() && st.top().second == id) {
auto pr = st.top().first;
int y = pr.first, sy = pr.second;
st.pop();
int x = par[y];
sz[x] -= sy;
par[y] = y;
}
}
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 &p : seg_pref[id]) {
int u=p.first, v=p.second;
int w = max(u,v);
if (join(u,v,id)) f1.update(1,0,a-1,w,a-1,-1);
}
if (l == r) {
for (auto &pr : pos[l]) {
int x = pr.first, qi = pr.second;
res[qi] = f1.get(1,0,a-1,x);
}
} else {
int mid=(l+r)>>1;
dfs_pref(id*2, l, mid);
dfs_pref(id*2+1, mid+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 &p : seg_suf[id]) {
int u=p.first, v=p.second;
int w = min(u,v);
if (join(u,v,id)) f1.update(1,0,a-1,0,w,-1);
}
if (l == r) {
for (auto &pr : pos[l]) {
int x = pr.first, qi = pr.second;
res[qi] += f1.get(1,0,a-1,x);
}
} else {
int mid=(l+r)>>1;
dfs_suf(id*2, l, mid);
dfs_suf(id*2+1, mid+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 {
int j = last[e];
vec.push_back({e.first,e.second,j,i-1});
last.erase(e);
}
}
for (auto &p:last) {
vec.push_back({p.first.first,p.first.second,p.second,b-1});
}
for (auto &e:vec) {
add_interval(seg_pref, 1, 0, b-1, e.l, e.r, {e.x,e.y});
add_interval(seg_suf, 1, 0, b-1, e.l, e.r, {e.x,e.y});
}
for (int i=0;i<c;i++) pos[w1[i]].push_back({w[i],i});
f1.init(a);
for (int x=0;x<a;x++) f1.update(1,0,a-1,x,a-1,1);
for (int i=0;i<a;i++){ par[i]=i; sz[i]=1; }
dfs_pref(1,0,b-1);
f1.init(a);
for (int x=0;x<a;x++) f1.update(1,0,a-1,0,x,1);
for (int i=0;i<a;i++){ par[i]=i; sz[i]=1; }
dfs_suf(1,0,b-1);
return res;
}
