Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- #include <iostream>
- #include <vector>
- #include <cstdio>
- #include <map>
- #include <complex>
- #include <algorithm>
- #include <math.h>
- #include <string>
- #include <cstring>
- #include <set>
- using namespace std;
- const int N = 300010;
- map<pair<int, int>, int> q;
- vector<int> quer;
- int ans[N];
- struct edge
- {
- int u, v, l, r;
- edge():
- u(0),
- v(0),
- l(0),
- r(0) {}
- edge(int u, int v, int l, int r):
- u(u),
- v(v),
- l(l),
- r(r) {}
- };
- vector<pair<pair<int, int>, pair<int, int> > > qq;
- vector<edge> edges;
- void add(int u, int v, int l, int r)
- {
- qq.push_back({{u, v}, {l, r}});
- }
- int pr[N], sz[N];
- vector<int> st;
- int curans;
- int findset(int v)
- {
- return ((v == pr[v]) ? v : findset(pr[v]));
- }
- int unionsets(int v, int u)
- {
- v = findset(v);
- u = findset(u);
- if (v == u)
- return 0;
- if (sz[v] < sz[u])
- swap(v, u);
- st.push_back(u);
- sz[v] += sz[u];
- pr[u] = v;
- curans--;
- return 1;
- }
- void remove()
- {
- int u = st.back();
- st.pop_back();
- sz[pr[u]] -= sz[u];
- pr[u] = u;
- curans++;
- }
- void divide(int l, int r, vector<edge> edges)
- {
- // cout << l << " " << r << " " << curans << endl;
- if (r < l)
- return;
- if (l == r)
- {
- ans[l] = curans;
- return;
- }
- int mid = (r + l) / 2;
- vector<edge> edges1;
- int num = 0;
- for (auto i : edges)
- {
- if (i.l > mid || i.r < l)
- continue;
- if (i.r >= mid && i.l <= l)
- num += unionsets(i.u, i.v);
- else
- edges1.push_back(i);
- }
- divide(l, mid, edges1);
- for (int i = 0; i < num; i++)
- remove();
- num = 0;
- edges1.clear();
- for (auto i : edges)
- {
- if (i.l > r || i.r <= mid)
- continue;
- if (i.l <= mid + 1 && i.r >= r)
- num += unionsets(i.u, i.v);
- else
- edges1.push_back(i);
- }
- divide(mid + 1, r, edges1);
- for (int i = 0; i < num; i++)
- remove();
- }
- int main()
- {
- // freopen("in.txt", "r", stdin);
- freopen("connect.in", "r", stdin); freopen("connect.out", "w", stdout);
- ios::sync_with_stdio(0);
- int n, k;
- cin >> n >> k;
- for (int i = 0; i < k; i++)
- {
- char c;
- cin >> c;
- if (c == '?')
- quer.push_back(i);
- else
- {
- int u, v;
- cin >> u >> v;
- if (u > v)
- swap(u, v);
- if (c == '+')
- q[make_pair(u, v)] = i;
- else
- {
- add(u, v, q[make_pair(u, v)], i);
- q.erase(make_pair(u, v));
- }
- }
- }
- if (n == 1)
- {
- for (int i = 0; i < quer.size(); i++)
- cout << "1\n";
- return 0;
- }
- for (auto it : q)
- {
- int u = it.first.first;
- int v = it.first.second;
- add(u, v, it.second, k);
- }
- add(1, 2, k + 1, k + 2);
- for (int i = 0; i < N; i++)
- pr[i] = i, sz[i] = 1;
- sort(qq.begin(), qq.end());
- for (auto i : qq)
- edges.push_back(edge(i.first.first, i.first.second, i.second.first, i.second.second));
- curans = n;
- divide(0, k + 2, edges);
- int j = 0;
- /* for (int i = 0; i < 10; i++)
- cout << ans[i] << " ";
- cout << endl << endl;*/
- for (int i = 0; i < quer.size(); i++)
- {
- // while (ans[j] < quer[i])
- // j++;
- cout << ans[quer[i]] << " ";
- }
- return 0;
- }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement