#include "collapse.h"
#include <algorithm>
#include <functional>
#include <stdlib.h>
#include <time.h>
#include <map>
using namespace std;
typedef pair<int, int> pii;
int n, c, q;
vector<pii> seg[1 << 18];
vector<pii> query[100001];
vector<int> ans;
void insertLine(int i, int s, int e, int x, int y, pii v) {
if (e < x || y < s) return;
if (x <= s && e <= y) {
seg[i].push_back(v);
return;
}
int m = (s + e) / 2;
insertLine(i << 1, s, m, x, y, v);
insertLine(i << 1 | 1, m + 1, e, x, y, v);
}
pii par1[100001];
int fen1[100001];
int sz1[100001];
pii par2[100001];
int fen2[100001];
int sz2[100001];
struct operate {
int * p;
int t;
int v;
};
void update(int fen[], int i, int v) {
while (i <= n) {
fen[i] += v;
i += i & -i;
}
}
int sum(int fen[], int i) {
int ret = 0;
while (i) {
ret += fen[i];
i -= i & -i;
}
return ret;
}
vector<operate> res;
void restore() {
operate i = res.back();
res.pop_back();
if (i.t != 0) {
update(i.p, i.v, i.t);
}
else {
*i.p = i.v;
}
}
int findDep(pii par[], int x) {
if (par[x].first) return findDep(par, par[x].first) + 1;
return 0;
}
int find(pii par[], int x, int t) {
if (par[x].second <= t) return find(par, par[x].first, t);
return x;
}
void saveSz(pii par[], int sz[], int x) {
while (x) {
res.push_back({ &sz[x], 0, sz[x] });
x = par[x].first;
}
}
void addSz(pii par[], int sz[], int x, int v) {
while (x) {
sz[x] += v;
x = par[x].first;
}
}
void merge(pii par[], int fen[], int sz[], int x, int y, int t) {
int px = find(par, x, t);
int py = find(par, y, t);
if (px == py) return;
if (sz[px] > sz[py]) swap(px, py);
pii nxt = par[px];
res.push_back({ &par[px].first, 0, nxt.first });
res.push_back({ &par[px].second, 0, nxt.second });
res.push_back({ fen, 1, nxt.second });
res.push_back({ fen, -1, t });
addSz(par, sz, nxt.first, -sz[px]);
par[px] = pii(py, t);
addSz(par, sz, py, sz[px]);
update(fen, nxt.second, -1);
update(fen, t, 1);
if (nxt.first) merge(par, fen, sz, nxt.first, py, nxt.second);
}
int answerQuery(int x) {
return sum(fen1, x) + sum(fen2, n - x);
}
void dnc(int i, int s, int e) {
int ps = res.size();
for (pii p : seg[i]) {
int x, y;
tie(x, y) = p;
++x; ++y;
saveSz(par1, sz1, x);
saveSz(par1, sz1, y);
saveSz(par2, sz2, x);
saveSz(par2, sz2, y);
merge(par1, fen1, sz1, x, y, y);
merge(par2, fen2, sz2, x, y, n - x + 1);
}
if (s == e) {
for (pii p : query[s]) {
ans[p.second] = n - answerQuery(p.first);
}
}
else {
int m = (s + e) / 2;
dnc(i << 1, s, m);
dnc(i << 1 | 1, m + 1, e);
}
while (ps < res.size()) restore();
}
const int inf = 1e6;
vector<int> simulateCollapse(int N, vector<int> T, vector<int> X,
vector<int> Y, vector<int> W, vector<int> P) {
for (int i = 1; i <= 100000; ++i) {
par1[i] = par2[i] = pii(0, inf);
sz1[i] = sz2[i] = 1;
}
n = N;
c = T.size();
q = W.size();
ans.resize(q);
{
map<pii, int> mp;
for (int i = 0; i < c; ++i) {
if (X[i] > Y[i]) swap(X[i], Y[i]);
if (T[i]) {
auto it = mp.find(pii(X[i], Y[i]));
insertLine(1, 1, c, it->second, i, pii(X[i], Y[i]));
mp.erase(it);
}
else {
mp[pii(X[i], Y[i])] = i + 1;
}
}
for (auto i : mp) {
insertLine(1, 1, c, i.second, c, i.first);
}
}
for (int i = 0; i < q; ++i) {
query[W[i] + 1].emplace_back(P[i] + 1, i);
}
dnc(1, 1, c);
return ans;
}
