fork download
copy 
  1. #include <bits/stdc++.h>
  2. using namespace std;
  3. #define faster ios_base::sync_with_stdio(false); cin.tie(NULL)
  4. #define Bit(mask , i) ((mask >> i) & 1)
  5. #define fi first
  6. #define se second
  7. #define _LOG2(nl) 31 - __builtin_clz(nl)
  8. #define c_bit(nl) __builtin_popcount(nl)
  9. #define ii pair<int , pair<int , int>>
  10. #define lii pair<long long , pair<int , int>>
  11. #define iii pair<int , pair<int , int>>
  12. #define li pair<long long , long long>
  13. #define db long double
  14. #define onBit(mask , i) (mask | (1 << i))
  15. #define offBit(mask , i) (mask & (~(1 << i)))
  16. #define reverseBit(mask , i) (mask ^ (1 << i))
  17. #define ill pair<int , pair<long long , long long>>
  18. #define lli pair<pair<long long , long long> , pair<int , int>>
  19.  
  20. const int N = 3e5 + 7;
  21. int n , q , par[N] , sz[N] , rollback_sz[4 * N] , ans[N] , cor;
  22. vector<pair<int , int>> t[4 * N];
  23.  
  24. struct gv{
  25.     int u , v , id;
  26. };
  27.  
  28. vector<gv> cand;
  29.  
  30. bool cmp(gv x , gv y){
  31.     if (x.u != y.u) return x.u < y.u;
  32.     if (x.v != y.v) return x.v < y.v;
  33.     return x.id < y.id;
  34. }
  35.  
  36. void update(int id , int l , int r , int L , int R , int u , int v){
  37.     if (l > R || r < L) return;
  38.     if (L <= l && r <= R){
  39.         t[id].push_back({u , v});
  40.         return;
  41.     }
  42.  
  43.     int mid = (l + r) >> 1;
  44.     update(id << 1 , l , mid , L , R , u , v);
  45.     update(id << 1 | 1 , mid + 1 , r , L , R , u , v);
  46. }
  47.  
  48. void inp(){
  49.     cin >> n >> q;
  50.     if (q == 0) exit(0);
  51.  
  52.     for (int i = 1 ; i <= n ; ++i){
  53.         par[i] = i;
  54.         sz[i] = 1;
  55.     }
  56.     cor = n;
  57.  
  58.     memset(ans , -1 , sizeof ans);
  59.     for (int i = 1 ; i <= q ; ++i){
  60.         char c;
  61.         cin >> c;
  62.         if (c == '?'){
  63.             ans[i] = 0;
  64.         }
  65.  
  66.         else{
  67.             int u , v;
  68.             cin >> u >> v;
  69.             if (u > v) swap(u , v);
  70.             cand.push_back({u , v , i});
  71.         }
  72.     }
  73.  
  74.     sort(cand.begin() , cand.end() , cmp);
  75.  
  76.     int i = 0;
  77.     while (i < cand.size()){
  78.         int j = i;
  79.         while (j < cand.size() - 1 && cand[i].u == cand[j + 1].u && cand[i].v == cand[j + 1].v){
  80.             ++j;
  81.             if ((j - i) % 2 == 1){
  82.                 update(1 , 1 , q , cand[j - 1].id , cand[j].id - 1 , cand[j].u , cand[j].v);
  83. //                cout << cand[j - 1].id << " " << cand[j].id - 1 << " " << cand[j].u << " " << cand[j].v << '\n';
  84.             }
  85.         }
  86.  
  87.         if ((j - i) % 2 == 0){
  88.             update(1 , 1 , q , cand[j].id , q , cand[j].u , cand[j].v);
  89. //            cout << cand[j].id << " " << q << " " << cand[j].u << " " << cand[j].v << '\n';
  90.         }
  91.  
  92.         i = j + 1;
  93.     }
  94. }
  95.  
  96. int find_par(int u){
  97.     if (u == par[u]) return u;
  98.     return find_par(par[u]);
  99. }
  100.  
  101. stack<pair<int , int>> rollback;
  102.  
  103. void Union(int id , int u , int v){
  104.     u = find_par(u) , v = find_par(v);
  105.     if (u == v) return;
  106.  
  107.     rollback.push({u , sz[u]});
  108.     rollback.push({v , sz[v]});
  109.  
  110.     --cor;
  111.     if (sz[v] > sz[u]) swap(u , v);
  112.     rollback_sz[id] += 2;
  113.     par[v] = u;
  114.     sz[u] += sz[v];
  115. }
  116.  
  117. void get_ans(int id , int l , int r){
  118.     for (auto &c : t[id]){
  119.         Union(id , c.fi , c.se);
  120.     }
  121.  
  122.     if (l == r){
  123.         if (ans[l] != -1) ans[l] = cor;
  124.     }
  125.  
  126.     else{
  127.         int mid = (l + r) >> 1;
  128.         get_ans(id << 1 , l , mid);
  129.         get_ans(id << 1 | 1 , mid + 1 , r);
  130.     }
  131.  
  132.     cor += rollback_sz[id] / 2;
  133.     while (rollback_sz[id] > 0){
  134.         auto c = rollback.top();
  135.         rollback.pop();
  136.  
  137.         par[c.fi] = c.fi;
  138.         sz[c.fi] = c.se;
  139.         --rollback_sz[id];
  140.     }
  141. }
  142.  
  143. void solve(){
  144.     get_ans(1 , 1 , q);
  145.     for (int i = 1 ; i <= q ; ++i) if (ans[i] != -1)
  146.         cout << ans[i] << '\n';
  147. }
  148.  
  149. int main(){
  150.     freopen("connect.in" , "r" , stdin);
  151.     freopen("connect.out" , "w" , stdout);
  152.     faster;
  153.     inp();
  154.     solve();
  155.     return 0;
  156. }
  157.  
Success #stdin #stdout 0.01s 33452KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
Standard output is empty
https://ideone.com/iXcm0Q
language:
C++14 (gcc 8.3)
created:
7 hours ago
visibility:
public

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!