#include <bits/stdc++.h>
#include "collapse.h"
using namespace std;
template<class T, class U>
void ckmin(T &a, U b)
{
if (a > b) a = b;
}
template<class T, class U>
void ckmax(T &a, U b)
{
if (a < b) a = b;
}
#define MP make_pair
#define PB push_back
#define LB lower_bound
#define UB upper_bound
#define fi first
#define se second
#define FOR(i, a, b) for (auto i = (a); i < (b); i++)
#define FORD(i, a, b) for (auto i = (a) - 1; i >= (b); i--)
#define SZ(x) ((int) (x).size())
#define ALL(x) (x).begin(), (x).end()
#define INF 1000000007
#define LLINF 2696969696969696969
#define MAXN 100013
typedef long long ll;
typedef long double ld;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;
typedef vector<int> vi;
typedef vector<ll> vl;
typedef vector<pii> vpi;
typedef vector<pll> vpl;
int N, D, Q, B;
vector<array<int, 4> > segments;
map<int, int> med[MAXN];
int ans[MAXN];
vpi segs[3 * MAXN];
int dsu[MAXN], siz[MAXN];
vector<array<int, 3> > undo;
int cc;
void ins(int w, int L, int R, int a, int b, pii p)
{
if (a <= L && R <= b)
{
segs[w].PB(p);
return;
}
int mid = (L + R) >> 1;
if (a <= mid) ins(w << 1, L, mid, a, b, p);
if (mid < b) ins(w << 1 | 1, mid + 1, R, a, b, p);
}
int get(int u)
{
return (u == dsu[u] ? u : get(dsu[u]));
}
void merge(int u, int v)
{
u = get(u);
v = get(v);
if (u == v) return;
if (siz[u] < siz[v]) swap(u, v);
undo.PB({u, v, siz[u]});
dsu[v] = u;
siz[u] += siz[v];
cc--;
return;
}
void solve(int w, int L, int R)
{
// cerr << "solve " << w << ' ' << L << ' ' << R << endl;
for (pii p : segs[w])
{
merge(p.fi, p.se);
}
auto cur = undo; undo.clear();
reverse(ALL(cur));
if (L == R)
{
ans[L] = cc;
}
else
{
int mid = (L + R) >> 1;
solve(w << 1, L, mid);
solve(w << 1 | 1, mid + 1, R);
}
for (auto e : cur)
{
dsu[e[1]] = e[1];
siz[e[0]] = e[2];
cc++;
}
return;
}
vi simulateCollapse(int n, vi t, vi x, vi y, vi w, vi p)
{
N = n; D = SZ(t); Q = SZ(w); B = p[0];
FOR(i, 0, D)
{
int u = x[i], v = y[i]; if (u > v) swap(u, v);
if (u <= B && B < v) continue;
if (t[i])
{
segments[med[u][v]][3] = i - 1;
}
else
{
med[u][v] = SZ(segments);
segments.PB({u, v, i, D - 1});
}
}
for (auto e : segments)
{
// cerr << e[0] << " -> " << e[1] << " lasts " << e[2] << " " << e[3] << endl;
ins(1, 0, D - 1, e[2], e[3], {e[0], e[1]});
}
cc = N;
FOR(i, 0, N)
{
dsu[i] = i;
siz[i] = 1;
}
solve(1, 0, D - 1);
vi res(Q);
// FOR(i, 0, D)
// {
// cerr << ans[i] << ' ';
// }
// cerr << endl;
FOR(i, 0, Q)
{
res[i] = ans[w[i]];
}
return res;
}
