#include <bits/stdc++.h>
#include "collapse.h"
using namespace std;
const int Bsize = 323, Nmax = 1e5 + 5;
struct Edge
{
int x, y, t1, t2;
bool operator < (const Edge &other) const
{
return y < other.y;
}
};
struct Query
{
int pos, t, id;
bool operator < (const Query &other) const
{
return pos < other.pos;
}
};
vector<int> answer;
vector<Query> queries;
vector<Edge> edges;
map< pair<int,int> , int > mp;
int N, Q, M;
namespace forest
{
static int moves;
static int t[Nmax], rang[Nmax];
static vector<int> S, T;
void init()
{
moves = 0;
S.clear(); T.clear();
int i;
for(i=0; i<N; ++i) t[i] = i;
}
int boss(int node)
{
while(t[node] != node) node = t[node];
return node;
}
bool unite(int x, int y)
{
x = boss(x); y = boss(y);
if(x == y) return 0;
++moves;
if(rang[x] == rang[y])
{
++rang[y];
S.push_back(y);
}
else
{
S.push_back(0);
if(rang[x] > rang[y]) swap(x, y);
}
t[x] = y;
T.push_back(x);
return 1;
}
void undo(int nr)
{
moves -= nr;
while(nr--)
{
assert(S.size());
assert(T.size());
int x, y;
x = T.back(), y = S.back();
S.pop_back(); T.pop_back();
t[x] = x;
if(y) rang[y] --;
}
}
}
void solve(vector<Edge> E, vector<Query> Q)
{
int i;
vector<Query> v[Nmax];
vector<Edge> all, possible;
for(auto it : Q)
v[it.t / Bsize * Bsize].push_back(it);
for(i=0; i<=M; i += Bsize) if(!v[i].empty())
{
forest::init();
all.clear();
possible.clear();
for(auto it : E)
if(it.t1 <= i && it.t2 >= i + Bsize - 1) all.push_back(it);
else if(it.t2 >= i && it.t1 <= i + Bsize - 1) possible.push_back(it);
sort(all.begin(), all.end());
sort(v[i].begin(), v[i].end());
int cursor = 0;
for(auto q : v[i])
{
while(cursor < all.size() && all[cursor].y <= q.pos)
forest::unite(all[cursor].x, all[cursor].y), ++cursor;
int undo = 0;
for(auto it : possible)
if(it.t1 <= q.t && q.t <= it.t2 && it.y <= q.pos)
if(forest::unite(it.x, it.y)) ++undo;
answer[q.id] -= forest::moves;
forest::undo(undo);
}
}
}
vector<int> simulateCollapse (int _N, vector<int> T, vector<int> X, vector<int> Y, vector<int> W, vector<int> P)
{
N = _N, M = T.size(), Q = W.size();
int i;
answer.resize(Q);
for(i=0; i<Q; ++i) answer[i] = N;
for(i=0; i<M; ++i)
{
if(X[i] > Y[i]) swap(X[i], Y[i]);
if(T[i] == 0) mp[{X[i], Y[i]}] = i;
else
{
edges.push_back({X[i], Y[i], mp[{X[i], Y[i]}], i - 1});
mp[{X[i], Y[i]}] = -1;
}
}
for(auto it : mp)
if(it.second != -1)
edges.push_back({it.first.first, it.first.second, it.second, M-1});
for(i=0; i<Q; ++i)
queries.push_back({P[i], W[i], i});
solve(edges, queries);
for(auto &it : edges)
{
it.x = N - it.x - 1, it.y = N - it.y - 1;
swap(it.x, it.y);
}
for(auto &it : queries)
it.pos = N - it.pos - 2;
solve(edges, queries);
return answer;
}
