Solution#

This is a template program for divide and conquer on a segment tree. The entire idea is that you build the time line into a segment tree and each edge exist for a certain time period on the tree. There are several details in implementation, please refer to the code.

Full Implementation#

// Eating, bathing, having a girlfriend, having an active social life is incidental, it gets in the way of code time.
// Writing code is the primary force that drives our lives so anything that interrupts that is wasteful.
#include <bits/stdc++.h>
using namespace std;
/************************************/
inline int64_t read() { int64_t x = 0, f = 1; char ch = getchar(); while (ch<'0'|| ch>'9') { if(ch == '-') f = -1; ch = getchar(); } while (ch >= '0' && ch <= '9') { x = x * 10 + ch - '0'; ch = getchar();} return x * f; }
inline int read(char *s) { char ch = getchar(); int i = 1; while (ch == ' ' || ch == '\n') ch = getchar(); while (ch != ' ' && ch != '\n') s[i++] = ch, ch = getchar(); s[i] = '\0'; return i - 1; }
#define fileio(x) freopen((string(x) + ".in").c_str(), "r", stdin), freopen((string(x) + ".out").c_str(), "w", stdout)
typedef int64_t ll; typedef pair<int, int> pii; typedef pair<ll, ll> pll; typedef long double ld;
ll mod = 1e9 + 7;
#define fi first
#define se second
ll fpow(ll a, ll b, ll md, ll cur = 1) { while (b) { { if (b % 2 == 1) cur *= a; } a *= a, b = b / 2, a %= md, cur %= md; } return cur % md; }
/************************************/
const int N = 3e5 + 5, inf = 0x3f3f3f3f;

int n, m, sum[N << 2];
struct node {
    int f, u, v;
    node(int _f = 0, int _u = 0, int _v = 0) { f = _f, u = _u, v = _v; }
} qry[N];

struct edg {
    int u, v;
    bool operator<(const edg &b) const { return u != b.u ? u < b.u : v < b.v; }
};

vector<edg> vec[N << 2];
map<edg, int> mp;

void maintain(int p) { sum[p] = sum[p << 1] + sum[p << 1 | 1]; }
void build(int p = 1, int l = 1, int r = m) {
    if (l >= r) {
        sum[p] = (qry[l].f == 2);
        return;
    }
    int mid = (l + r) >> 1;
    build(p << 1, l, mid), build(p << 1 | 1, mid + 1, r), maintain(p);
}
void upd(int L, int R, edg x, int p = 1, int l = 1, int r = m) {
    if (l >= L && r <= R) {
        vec[p].emplace_back(x);
        return;
    }
    if (l > R || r < L)
        return;
    int mid = (l + r) >> 1;
    upd(L, R, x, p << 1, l, mid), upd(L, R, x, p << 1 | 1, mid + 1, r);
}

int par[N << 1];
int siz[N << 1];
int sol = 0;
vector<pii> hsty;
inline void init() {
    for (int i = 1; i <= n; i++) {
        par[i] = i;
        siz[i] = 1;
    }
    sol = n;
}

int find(int x) {
	if (par[x] == x) return x;
	return find(par[x]);
}

void merge(int a, int b) {
	a = find(a);
	b = find(b);
	if (a != b) {
		sol--;
		if (siz[a] > siz[b]) {
			swap(a, b);
		}
		siz[b] += siz[a];
		par[a] = b;
		hsty.push_back({a, b});
	}
}

int snap() {
	return hsty.size();
}

void rlb(int stp) {
	while (hsty.size() > stp) {
		int a = hsty.back().first;
		int b = hsty.back().second;
		sol++;
		siz[b] -= siz[a];
		par[a] = a;
		hsty.pop_back();
	}
}

void dvc(int p = 1, int l = 1, int r = m) {
    if (!sum[p])
        return;
    int now = snap();
    for (edg &x : vec[p])
        merge(x.u, x.v);
    if (l >= r) {
        cout << sol << '\n';
        rlb(now);
        return;
    }
    int mid = (l + r) >> 1;
    dvc(p << 1, l, mid), dvc(p << 1 | 1, mid + 1, r);
    rlb(now);
    return;
}

signed main() {
#ifndef LOCAL
    fileio("connect");
#endif

    ios::sync_with_stdio(0);
    cin.tie(0), cout.tie(0);

    cin >> n >> m;
    init();
    char op;
    int u, v;
    for (int i = 1; i <= m; i++) {
        cin >> op;
        if (op == '?') {
            qry[i] = node(2, 0, 0);
        } else {
            cin >> u >> v;
            if (u > v)
                swap(u, v);
            qry[i] = node(op != '+', u, v);
        }
    }

    for (int i = 1; i <= m; i++) {
        edg x = {qry[i].u, qry[i].v};
        if (qry[i].f == 0)
            mp[x] = i;
        if (qry[i].f == 1) {
            int l = mp[x], r = i - 1;
            upd(l, r, x);
            mp.erase(x);
        }
    }

    for (auto &[a, b] : mp)
        upd(b, m, a);

    build();
    dvc();

    return 0;
}