#include <bits/stdc++.h>
#include "collapse.h"
using namespace std;
typedef long long ll;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;
//#define debug(...) fprintf(stderr, __VA_ARGS__)
#define debug(...)
#define fi first
#define se second
#define all(v) (v).begin(), (v).end()
#define fillchar(a, s) memset((a), (s), sizeof(a))
int N, C, Q;
namespace subtask1 {
const int MAXN = 5010;
struct union_find {
int par[100320]; //don't forget to init
int ncomp;
int find (int x) {
return x == par[x] ? x : par[x] = find(par[x]);
}
bool merge (int x, int y) {
x = find(x);
y = find(y);
if (x == y) {
return false;
}
par[x] = y;
ncomp--;
return true;
}
void reset (int sz) {
for (int i = 0; i < sz; i++) {
par[i] = i;
}
ncomp = sz;
}
};
map<pii, int> mpind;
bitset<MAXN> active[MAXN];
union_find uf;
vector<int> go (vector<int> T, vector<int> X, vector<int> Y, vector<int> W, vector<int> P) {
for (int i = 0; i < C; i++) {
if (i) {
active[i] = active[i - 1];
}
int indxy;
if (mpind.count(pii(X[i], Y[i]))) {
indxy = mpind[pii(X[i], Y[i])];
} else {
indxy = mpind[pii(X[i], Y[i])] = i;
}
if (T[i] == 0) {
active[i][indxy] = true;
} else {
active[i][indxy] = false;
}
}
vector<int> ans;
for (int i = 0; i < Q; i++) {
uf.reset(N);
//day W[i]
for (int j = 0; j < C; j++) {
if (active[W[i]][j]) {
if (!(X[j] <= P[i] && P[i] + 1 <= Y[j])) {
uf.merge(X[j], Y[j]);
debug("avail %d %d\n", X[j], Y[j]);
}
}
}
debug("warm\n");
ans.push_back(uf.ncomp);
}
return ans;
}
}
//should have gotten this...too bad not enough time.
namespace subtask2 {
const int MAXN = 1 << 17;
struct union_find {
int par[MAXN], sz[MAXN]; //don't forget to init
int ncmp;
pair<int*, int> stk[MAXN * 34];
int stksz;
void init (int n) {
ncmp = n;
for (int i = 0; i < n; i++) {
par[i] = i;
sz[i] = 1;
}
stksz = 0;
}
int find (int x) {
return x == par[x] ? x : find(par[x]);
}
void change (int &x, int y) {
stk[stksz++] = make_pair(&x, x);
x = y;
}
void merge (int x, int y) {
x = find(x);
y = find(y);
if (x == y) {
return;
}
if (sz[x] > sz[y]) {
swap(x, y);
}
change(sz[y], sz[y] + sz[x]);
change(par[x], y);
change(ncmp, ncmp - 1);
}
void rollback (int s) {
while (stksz > s) {
auto p = stk[--stksz];
*(p.fi) = p.se;
}
}
};
union_find uf;
int seglt[2 * MAXN], segrt[2 * MAXN];
vector<pii> tree[2 * MAXN];
void update (int a, int b, pii v, int cur = 1) {
int lt = seglt[cur], rt = segrt[cur];
if (rt <= a || b <= lt) {
return;
}
if (a <= lt && rt <= b) {
tree[cur].push_back(v);
return;
}
update(a, b, v, 2 * cur);
update(a, b, v, 2 * cur + 1);
}
int P;
int ncompt[MAXN]; //number of components at this time
void calcseg (int cur = 1, int lt = 0, int rt = MAXN) {
seglt[cur] = lt;
segrt[cur] = rt;
int mid = (lt + rt) >> 1;
if (rt - lt > 1) {
calcseg((cur << 1), lt, mid);
calcseg((cur << 1) | 1, mid, rt);
}
}
void dfs (int cur = 1) {
int lt = seglt[cur], rt = segrt[cur];
if (lt >= C) {
return;
}
int state = uf.stksz;
//add edges
for (pii e : tree[cur]) {
uf.merge(e.fi, e.se);
}
if (rt - lt == 1) {
ncompt[lt] = uf.ncmp;
} else {
dfs(cur << 1);
dfs((cur << 1) | 1);
}
uf.rollback(state);
}
vector<int> go (vector<int> T, vector<int> X, vector<int> Y, vector<int> W, int ppppp) {
uf.init(N);
P = ppppp;
map<pii, int> mp;
calcseg();
for (int i = 0; i < C; i++) {
pii e(X[i], Y[i]);
if (X[i] <= P && P + 1 <= Y[i]) {
continue;
}
if (mp.count(e)) {
update(mp.at(e), i, e);
mp.erase(e);
} else {
mp[e] = i;
}
}
debug("here\n");
for (auto it : mp) {
update(it.se, C, it.fi);
}
//ok let's go!
dfs();
vector<int> ans;
for (int day : W) {
ans.push_back(ncompt[day]);
}
return ans;
}
}
namespace subtask3 {
const int MAXN = 1e5 + 320;
const int SQRT = 320;
//6s, 512MB
struct union_find {
int par[MAXN];
vector<pair<int*, int>> chng;
bool active;
int ncomp;
void reset() {
for (int i = 0; i < N; i++) {
par[i] = i;
}
ncomp = N;
chng.clear();
active = false;
}
void change (int &x, int y) {
if (active) {
chng.push_back(make_pair(&x, x));
}
x = y;
}
int find (int x) {
if (x == par[x]) {
return x;
}
change(par[x], find(par[x]));
return par[x];
}
void merge (int x, int y) {
x = find(x);
y = find(y);
if (x == y) {
return;
}
change(par[x], y);
change(ncomp, ncomp - 1);
}
void rollback() {
for (auto p : chng) {
*(p.fi) = p.se;
}
chng.clear();
}
};
vector<pii> queries[MAXN]; //queries[day] = vector(position, id)
int ans[MAXN];
union_find uf;
pii estl[MAXN], estr[MAXN], tmp[MAXN];
bool cmpr (pii p1, pii p2) {
return p1.se < p2.se;
}
bool cmpl (pii p1, pii p2) {
return p1.fi > p2.fi;
}
vector<int> go (vector<int> X, vector<int> Y, vector<int> W, vector<int> P) {
//X, Y = roads constructed
//w, P = questions.
for (int i = 0; i < Q; i++) {
queries[W[i]].push_back({P[i], i});
}
for (int sday = 0; sday < C; sday += SQRT) {
int eday = min(sday + SQRT, C);
//what is the stuff before sday? certainly need to add this in.
vector<array<int, 3>> vqu;
for (int i = sday; i < eday; i++) {
for (pii p : queries[i]) {
vqu.push_back({p.fi, i, p.se});
}
}
//ok let's now go to this now.
int posr = 0; //position of estr
//prefix
debug("-------start prefix----------\n");
sort(all(vqu));
uf.reset();
for (auto q : vqu) {
int pos = q[0];
for (; posr < sday && estr[posr].se <= q[0]; posr++) {
uf.merge(estr[posr].fi, estr[posr].se);
debug("merge %d %d\n", estr[posr].fi, estr[posr].se);
}
//need this
for (int i = sday; i < eday; i++) {
uf.find(X[i]);
uf.find(Y[i]);
}
uf.active = true;
debug("--active--\n");
//then merge the rest of them!
for (int i = sday; i <= q[1]; i++) {
//is this a valid merge?
if (Y[i] <= pos) {
uf.merge(X[i], Y[i]);
debug("merge %d %d\n", X[i], Y[i]);
}
}
ans[q[2]] += uf.ncomp;
debug("answer[%d] += %d\n", q[2], uf.ncomp);
uf.rollback();
uf.active = false;
debug("--inactive--\n");
}
debug("-------start suffix----------\n");
//suffix
uf.reset();
reverse(all(vqu));
int posl = 0;
for (auto q : vqu) {
int pos = q[0];
//note: strictly greater than q[0]
for (; posl < sday && estl[posl].fi > q[0]; posl++) {
uf.merge(estl[posl].fi, estl[posl].se);
debug("merge %d %d\n", estl[posl].fi, estl[posl].se);
}
//need this
for (int i = sday; i < eday; i++) {
uf.find(X[i]);
uf.find(Y[i]);
}
debug("--active--\n");
uf.active = true;
for (int i = sday; i <= q[1]; i++) {
if (X[i] > pos) {
uf.merge(X[i], Y[i]);
debug("merge %d %d\n", X[i], Y[i]);
}
}
ans[q[2]] += uf.ncomp - N;
debug("answer[%d] += %d; answer[%d] -= N\n", q[2], uf.ncomp, q[2]);
uf.rollback();
debug("--inactive--\n");
uf.active = false;
}
//then add the new edges
vector<pii> nedge;
for (int i = sday; i < eday; i++) {
nedge.push_back({X[i], Y[i]});
}
sort(all(nedge), cmpl);
copy(tmp, merge(estl, estl + sday, all(nedge), tmp, cmpl), estl);
sort(all(nedge), cmpr);
copy(tmp, merge(estr, estr + sday, all(nedge), tmp, cmpr), estr);
}
return vector<int> (ans, ans + Q);
}
}
vector<int> simulateCollapse (int n, vector<int> T, vector<int> X, vector<int> Y, vector<int> W, vector<int> P) {
N = n;
C = X.size();
Q = W.size();
for (int i = 0; i < C; i++) {
if (X[i] > Y[i]) {
swap(X[i], Y[i]);
}
}
if (N <= 5000 && Q <= 5000) {
return subtask1::go(T, X, Y, W, P);
} else if ((set<int> (all(P))).size() == 1) {
return subtask2::go(T, X, Y, W, P[0]);
} else if (count(all(T), 0) == T.size()) {
}
}
