#include<bits/stdc++.h>
#include<fstream>
using namespace std;
//#pragma GCC optimize("Ofast,unroll-loops")
//#pragma GCC target("avx2,tune=native")
//huhu
#define sz(a) (int)a.size()
#define ALL(v) v.begin(), v.end()
#define ALLR(v) v.rbegin(), v.rend()
#define ll long long
#define pb push_back
#define forr(i, a, b) for(int i = a; i < b; i++)
#define dorr(i, a, b) for(int i = a; i >= b; i--)
#define ld long double
#define vt vector
#include<fstream>
#define fi first
#define se second
#define pll pair<ll, ll>
#define pii pair<int, int>
#define mpp make_pair
#define ull unsigned long long
const int mxn = 1e5 + 5, inf = 1e9 + 5, sq = 350;
#include "collapse.h"
int n;
struct DSU{
int pa[mxn + 1];
vt<int>comp;
void init(){
for(int i = 0; i < n; i++)pa[i] = -1;
}
int fp(int u){
if(pa[u] < 0)return(u);
return(pa[u] = fp(pa[u]));
}
bool unon(int u, int v){
comp.pb(u); comp.pb(v);
u = fp(u); v = fp(v);
if(u == v)return(0);
if(-pa[u] < -pa[v])swap(u, v);
pa[u] += pa[v]; pa[v] = u;
return(1);
}
void reset(){
for(auto i: comp){
pa[i] = -1;
}
comp.clear();
}
};
struct Q{
int tme, p, id;
bool operator <(const Q &other){
return(p < other.p);
}
};
vt<Q>queries;
bool cmpl(pii a, pii b){
return(a.se < b.se);
}
bool cmpr(pii a, pii b){
return(a.fi > b.fi);
}
vt<int>t, x, y, w, p, res;
set<pair<int, int>>all; // edges after block[i - 1]
vt<pii>inblock[mxn + 1]; // edges that appear in block
void solve(int l, int r){
set<pair<int, int>>remain = all;
for(int i = l; i <= r; i++){
if(t[i] == 1 && remain.count(mpp(x[i], y[i]))){
remain.erase(mpp(x[i], y[i]));
}
}
map<pair<int, int>, int>last;
for(int i = l; i <= r; i++){
if(t[i] == 0){
assert(last.find(mpp(x[i], y[i])) == last.end());
last[mpp(x[i], y[i])] = i;
}else{
int lt = ((last.find(mpp(x[i], y[i])) == last.end()) ? l : last[mpp(x[i], y[i])]);
for(int j = lt; j < i; j++){
inblock[j].pb(mpp(x[i], y[i]));
}
last.erase(mpp(x[i], y[i]));
}
}
for(auto i: last){
for(int j = i.se; j <= r; j++){
inblock[j].pb(i.fi);
}
}
vt<pii>edge;
for(auto i: remain)edge.pb(i);
sort(ALL(edge), cmpl);
vt<Q>curr;
for(auto i: queries){
if(i.tme >= l && i.tme <= r){
curr.pb({i.tme, i.p, i.id});
}
}
sort(ALL(curr));
int lp = 0;
DSU dsu, dsu2; dsu.init(); dsu2.init();
int cnt = 0; //global connection
for(auto [tme, pl, id]: curr){
while(lp < sz(edge) && edge[lp].se <= pl){
cnt += dsu.unon(edge[lp].fi, edge[lp].se); lp++;
}
int cnt2 = cnt; // connection for this query only
for(auto [u, v]: inblock[tme]){
if(v <= pl){
cnt2 += dsu2.unon(dsu.fp(u), dsu.fp(v));
}
}
dsu2.reset();
res[id] += (pl) - cnt2;
}
dsu.init(); dsu2.init();
curr.clear();
// same thing but for right side :>
for(auto i: queries){
if(i.tme >= l && i.tme <= r){
curr.pb({i.tme, i.p + 1, i.id});
}
}
sort(ALLR(curr));
sort(ALL(edge), cmpr);
int rp = 0;
cnt = 0; //global connection
for(auto [tme, pr, id]: curr){
while(rp < sz(edge) && edge[rp].fi >= pr){
cnt += dsu.unon(edge[rp].fi, edge[rp].se); rp++;
}
int cnt2 = cnt; // connection for this query only
for(auto [u, v]: inblock[tme]){
if(u >= pr){
cnt2 += dsu2.unon(dsu.fp(u), dsu.fp(v));
}
}
dsu2.reset();
res[id] += (n - pr + 1) - cnt2;
}
for(int i = l; i <= r; i++){
if(t[i] == 0)all.insert(mpp(x[i], y[i]));
else all.erase(mpp(x[i], y[i]));
}
}
/*
std::vector<int> simulateCollapse(
int N,
std::vector<int> T,
std::vector<int> X,
std::vector<int> Y,
std::vector<int> W,
std::vector<int> P
) {
n = N; t = T; x = X; y = Y; w = W; p = P;
for(int i = 0; i < sz(x); i++){
if(x[i] > y[i])swap(x[i], y[i]);
}
for(int i = 0; i < sz(w); i++){
queries.pb({w[i], p[i], i});
}
res.resize(sz(queries));
int l = 0;
for(int i = 0; i < sz(t); i += sq){
solve(i, min(i + sq - 1, sz(t) - 1));
}
return(res);
}
int main(int argc, char *argv[]) {
int N, C, Q;
scanf("%d%d%d", &N, &C, &Q);
std::vector<int> T(C), X(C), Y(C);
for(int i = 0; i < C; i++) {
scanf("%d%d%d", &T[i], &X[i], &Y[i]);
}
std::vector<int> W(Q), P(Q);
for(int i = 0; i < Q; i++) {
scanf("%d%d", &W[i], &P[i]);
}
auto res = simulateCollapse(N, T, X, Y, W, P);
for(auto i : res) {
printf("%d\n", i);
}
}
*/
Compilation message
collapse.cpp: In function 'void solve(int, int)':
collapse.cpp:109:14: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
109 | for(auto [tme, pl, id]: curr){
| ^
collapse.cpp:114:18: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
114 | for(auto [u, v]: inblock[tme]){
| ^
collapse.cpp:134:14: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
134 | for(auto [tme, pr, id]: curr){
| ^
collapse.cpp:139:18: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
139 | for(auto [u, v]: inblock[tme]){
| ^
/usr/bin/ld: /tmp/ccNn3SfZ.o: in function `main':
grader.cpp:(.text.startup+0x227): undefined reference to `simulateCollapse(int, std::vector<int, std::allocator<int> >, std::vector<int, std::allocator<int> >, std::vector<int, std::allocator<int> >, std::vector<int, std::allocator<int> >, std::vector<int, std::allocator<int> >)'
collect2: error: ld returned 1 exit status
