peltorator

!DCP

Jan 28th, 2018
78
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  1. #include <iostream>
  2. #include <vector>
  3. #include <cstdio>
  4. #include <map>
  5. #include <complex>
  6. #include <algorithm>
  7. #include <math.h>
  8. #include <string>
  9. #include <cstring>
  10. #include <set>
  11.  
  12.  
  13. using namespace std;
  14.  
  15. const int N = 300010;
  16.  
  17. map<pair<int, int>, int> q;
  18. vector<int> quer;
  19. int ans[N];
  20.  
  21. struct edge
  22. {
  23.     int u, v, l, r;
  24.     edge():
  25.         u(0),
  26.         v(0),
  27.         l(0),
  28.         r(0) {}
  29.     edge(int u, int v, int l, int r):
  30.         u(u),
  31.         v(v),
  32.         l(l),
  33.         r(r) {}
  34. };
  35.  
  36. vector<pair<pair<int, int>, pair<int, int> > > qq;
  37. vector<edge> edges;
  38.  
  39. void add(int u, int v, int l, int r)
  40. {
  41.     qq.push_back({{u, v}, {l, r}});
  42. }
  43.  
  44. int pr[N], sz[N];
  45.  
  46. vector<int> st;
  47.  
  48. int curans;
  49.  
  50. int findset(int v)
  51. {
  52.     return ((v == pr[v]) ? v : findset(pr[v]));
  53. }
  54.  
  55.  
  56. int unionsets(int v, int u)
  57. {
  58.     v = findset(v);
  59.     u = findset(u);
  60.     if (v == u)
  61.         return 0;
  62.     if (sz[v] < sz[u])
  63.         swap(v, u);
  64.     st.push_back(u);
  65.     sz[v] += sz[u];
  66.     pr[u] = v;
  67.     curans--;
  68.     return 1;
  69. }
  70.  
  71. void remove()
  72. {
  73.     int u = st.back();
  74.     st.pop_back();
  75.     sz[pr[u]] -= sz[u];
  76.     pr[u] = u;
  77.     curans++;
  78. }
  79.  
  80. void divide(int l, int r, vector<edge> edges)
  81. {
  82.   //  cout << l << " " << r << " " << curans << endl;
  83.     if (r < l)
  84.         return;
  85.     if (l == r)
  86.     {
  87.         ans[l] = curans;
  88.         return;
  89.     }
  90.     int mid = (r + l) / 2;
  91.     vector<edge> edges1;
  92.     int num = 0;
  93.     for (auto i : edges)
  94.     {
  95.         if (i.l > mid || i.r < l)
  96.             continue;
  97.         if (i.r >= mid && i.l <= l)
  98.             num += unionsets(i.u, i.v);
  99.         else
  100.             edges1.push_back(i);
  101.     }
  102.     divide(l, mid, edges1);
  103.     for (int i = 0; i < num; i++)
  104.         remove();
  105.     num = 0;
  106.     edges1.clear();
  107.     for (auto i : edges)
  108.     {
  109.         if (i.l > r || i.r <= mid)
  110.             continue;
  111.         if (i.l <= mid + 1 && i.r >= r)
  112.             num += unionsets(i.u, i.v);
  113.         else
  114.             edges1.push_back(i);
  115.     }
  116.     divide(mid + 1, r, edges1);
  117.     for (int i = 0; i < num; i++)
  118.         remove();
  119. }
  120.  
  121. int main()
  122. {
  123. //    freopen("in.txt", "r", stdin);
  124. freopen("connect.in", "r", stdin); freopen("connect.out", "w", stdout);
  125.     ios::sync_with_stdio(0);
  126.     int n, k;
  127.     cin >> n >> k;
  128.     for (int i = 0; i < k; i++)
  129.     {
  130.         char c;
  131.         cin >> c;
  132.         if (c == '?')
  133.             quer.push_back(i);
  134.         else
  135.         {
  136.             int u, v;
  137.             cin >> u >> v;
  138.             if (u > v)
  139.                 swap(u, v);
  140.             if (c == '+')
  141.                 q[make_pair(u, v)] = i;
  142.             else
  143.             {
  144.                 add(u, v, q[make_pair(u, v)], i);
  145.                 q.erase(make_pair(u, v));
  146.             }
  147.         }
  148.     }
  149.     if (n == 1)
  150.     {
  151.         for (int i = 0; i < quer.size(); i++)
  152.             cout << "1\n";
  153.         return 0;
  154.     }
  155.     for (auto it : q)
  156.     {
  157.         int u = it.first.first;
  158.         int v = it.first.second;
  159.         add(u, v, it.second, k);
  160.     }
  161.     add(1, 2, k + 1, k + 2);
  162.     for (int i = 0; i < N; i++)
  163.         pr[i] = i, sz[i] = 1;
  164.     sort(qq.begin(), qq.end());
  165.     for (auto i : qq)
  166.         edges.push_back(edge(i.first.first, i.first.second, i.second.first, i.second.second));
  167.     curans = n;
  168.     divide(0, k + 2, edges);
  169.     int j = 0;
  170.   /*  for (int i = 0; i < 10; i++)
  171.         cout << ans[i] << " ";
  172.     cout << endl << endl;*/
  173.     for (int i = 0; i < quer.size(); i++)
  174.     {
  175.       //  while (ans[j] < quer[i])
  176.         //    j++;
  177.         cout << ans[quer[i]] << " ";
  178.     }
  179.     return 0;
  180. }
RAW Paste Data