#include "collapse.h"
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
const int sq = 350;
struct UnionFind {
vector<int> P, S;
int N;
vector<array<int, 2>> rb;
UnionFind(int N): N(N), P(N), S(N, 1) { iota(P.begin(), P.end(), 0); }
int find(int x) { return x == P[x] ? x : find(P[x]); }
void merge(int x, int y) {
if((x = find(x)) == (y = find(y))) return;
if(S[x] > S[y]) swap(x, y);
S[y] += S[x], P[x] = P[y];
rb.push_back({x, y});
}
void rollBack(int k) {
while(rb.size() > k) {
auto [x, y] = rb.back(); rb.pop_back();
S[y] -= S[x], P[x] = x;
}
}
};
void solve(int N, int M, vector<int> &T, vector<int> &X, vector<int> &Y, vector<int> &W, vector<int> &P, vector<int> &re) {
int K = X.size();
int C = (K-1)/sq+1;
vector<vector<array<int, 3>>> Q(C);
for(int i=0;i<M;i++) Q[W[i]/sq].push_back({P[i], W[i], i});
vector<array<int, 3>> V(K);
for(int i=0;i<K;i++) V[i] = {min(X[i], Y[i]), max(X[i], Y[i]), i};
sort(V.begin(), V.end());
vector<array<int, 4>> E;
for(int i=0;i<K;i++) {
auto [x, y, t] = V[i];
int j = i;
while(j+1 < K && V[j+1][0] == x && V[j+1][1] == y) j++;
for(int k=i;k<=j;k+=2) E.push_back({x, y, V[k][2], k == j ? K : V[k+1][2]-1});
i = j;
}
for(int i=0;i<C;i++) {
int L = i*sq, R = min(L+sq-1, K-1);
vector<vector<int>> s(N);
vector<array<int, 4>> sp;
for(auto [x, y, l, r] : E) {
if(l <= L && R <= r) s[y].push_back(x);
else if(L <= r || l <= R) sp.push_back({x, y, l, r});
}
sort(Q[i].begin(), Q[i].end());
UnionFind uf(N);
for(int j=0, k=0;j<N-1;j++) {
for(auto L : s[j]) uf.merge(L, j);
while(k < Q[i].size() && Q[i][k][0] == j) {
auto [P, W, id] = Q[i][k++];
int rev = uf.rb.size();
for(auto [x, y, l, r] : sp) if(l <= W && W <= r && max(x, y) <= P) uf.merge(x, y);
re[id] -= uf.rb.size();
uf.rollBack(rev);
}
}
}
}
vector<int> simulateCollapse(int N, vector<int> T, vector<int> X, vector<int> Y, vector<int> W, vector<int> P) {
int M = W.size();
vector<int> re(M, N);
solve(N, M, T, X, Y, W, P, re);
for(int i=0;i<X.size();i++) X[i] = N-X[i]-1, Y[i] = N-Y[i]-1;
for(int i=0;i<M;i++) P[i] = N-P[i]-2;
solve(N, M, T, X, Y, W, P, re);
return re;
}
