#include <iostream>
#include <fstream>
#include <vector>
#include <set>
#include <map>
#include <cstring>
#include <string>
#include <cmath>
#include <cassert>
#include <ctime>
#include <algorithm>
#include <sstream>
#include <list>
#include <queue>
#include <deque>
#include <stack>
#include <cstdlib>
#include <cstdio>
#include <iterator>
#include <functional>
#include <unordered_set>
#include <unordered_map>
#include <stdio.h>
#include <bitset>
using namespace std;
#define ll long long
#define pb push_back
#define mp make_pair
#define f first
#define s second
const ll maxn = 3e5 + 5, maxm = 5e6 + 1;
const ll mod = 998244353, inf = 1e9;
int n, m;
int u[maxn], v[maxn], lf[maxn], rg[maxn], ans[maxn];
char c[maxn];
map<pair<int, int>, int> was;
struct dsu{
int comps;
int p[maxn], sz[maxn];
stack<int> s;
void init(){
for (int i = 1; i <= n; ++i){
p[i] = i, sz[i] = 1;
}
comps = n;
}
int get(int v){
return (v == p[v] ? v : get(p[v]));
}
void unite(int a, int b){
a = get(a);
b = get(b);
if (a == b)
return;
if (sz[a] > sz[b])
swap(a, b);
sz[b] += sz[a];
p[a] = b;
comps -= 1;
s.push(a);
}
void rollback(int x){
sz[p[x]] -= sz[x];
p[x] = x;
comps += 1;
}
} t;
void go(int l = 1, int r = m){
if (l == r){
ans[l] = t.comps;
return;
}
int z = t.s.size(), mid = (l + r) / 2;
for (int i = mid; i <= r; ++i){
if (lf[i] <= l){
t.unite(u[i], v[i]);
}
}
go(l, mid);
while (t.s.size() != z){
int y = t.s.top();
t.rollback(y);
t.s.pop();
}
for (int i = l; i <= mid + 1; ++i){
if (rg[i] >= r){
t.unite(u[i], v[i]);
}
}
go(mid + 1, r);
while (t.s.size() != z){
int y = t.s.top();
t.rollback(y);
t.s.pop();
}
}
int main(){
// freopen("poetry.in", "r", stdin);
// freopen("poetry.out", "w", stdout);
ios_base::sync_with_stdio(false);
cin.tie(0);
cout.tie(0);
cin >> n >> m;
t.init();
for (int i = 1; i <= m; ++i){
cin >> c[i];
if (c[i] == '?'){
lf[i] = inf;
rg[i] = -inf;
}
else{
cin >> u[i] >> v[i];
if (u[i] > v[i])
swap(u[i], v[i]);
if (c[i] == '-'){
int x = was[mp(u[i], v[i])];
lf[i] = x;
rg[x] = i;
rg[i] = -inf;
was[mp(u[i], v[i])] = 0;
}
else{
was[mp(u[i], v[i])] = i;
lf[i] = inf;
rg[i] = m;
}
}
}
go();
for (int i = 1; i <= m; ++i){
if (c[i] == '?'){
cout << ans[i] << '\n';
}
}
}
Хотел попробовать написать dco по другому(без дерева отрезков). но почему то это ловит мл.
Задача: Courses - Codeforces
