fork download
copy 
  1. #include <bits/stdc++.h>
  2. #define ll int
  3. #define ld long double
  4. #define el "\n"
  5. #define _ROOT_ int main()
  6. #pragma GCC optimize("O2")
  7. #define FOR(i,l,r) for(int i = l ; i <= r ; i ++)
  8. #define FORD(i,r,l) for(int i = r ; i >= l ; i --)
  9. #define REP(i, a ) for(int i = 0 ; i < a ; i ++ )
  10. #define fi first
  11. #define se second
  12. #define M 1000000007
  13. #define MAXN 300001
  14. #define PI acos(-1)
  15. #define INF (1ll<<30)
  16. #define BLOCK_SIZE 425
  17. #define LOG 19
  18. #define BASE 256
  19. #define NAME "file"
  20. #define compare(v) sort((v).begin(), (v).end()); (v).erase(unique((v).begin(), (v).end()), (v).end());
  21. using namespace std;
  22. const ll MOD[] = {(ll)1e9 + 2277, (ll)1e9 + 5277, (ll)1e9 + 8277, (ll)1e9 + 9277, (ll) 1e9 + 7 };
  23. const ll NMOD = 1;
  24. //**Variable**//
  25. ll n, q ;
  26. ll scc ;
  27. ll arr[MAXN];
  28. ll res[MAXN] ;
  29. map<pair<ll,ll>, stack<ll> > mp ;
  30.  
  31. //**Struct**//
  32. struct Data {
  33.     ll u, sz ;
  34. };
  35. stack<Data> his ;
  36. struct Query {
  37.     ll u, v, t ;
  38.  
  39. } que[MAXN];
  40.  
  41. ll lab[MAXN] ;
  42. ll find_set(ll a ) {
  43.     return lab[a]  < 0 ? a : find_set(lab[a]);
  44. }
  45. bool union_set(ll u,ll v ) {
  46.     u = find_set(u) ;
  47.     v = find_set(v) ;
  48.     if(u == v ) return false ;
  49.     if(lab[u] > lab[v] ) swap(u, v ) ;
  50.     his.push({u, lab[u]}) ;
  51.     his.push({v, lab[v]}) ;
  52.     lab[u] += lab[v] ;
  53.     lab[v] = u ;
  54.     scc -- ;
  55.     return true;
  56. }
  57. void roll_back_dsu() {
  58.     if(his.empty() ) return ;
  59.     Data u = his.top() ;
  60.     his.pop() ;
  61.     lab[u.u] = u.sz ;
  62.     u = his.top() ;
  63.     his.pop() ;
  64.     lab[u.u] = u.sz ;
  65.     scc ++ ;
  66. }
  67. struct Seg {
  68.     vector<pair<ll,ll >> st[MAXN << 2 ] ;
  69.     void update(ll id, ll l, ll r, ll u, ll v, pair<ll,ll > key  ) {
  70.         if(u > r || v < l ) return ;
  71.         if(u <= l && v >= r ) {
  72.             st[id].push_back(key) ;
  73.             return ;
  74.         }
  75.         ll m = l + r >> 1 ;
  76.         update(id << 1, l, m, u, v,key ) ;
  77.         update(id << 1 | 1, m + 1, r, u, v, key ) ;
  78.     }
  79.  
  80.     void get(ll id, ll l, ll r  ) {
  81.         ll cnt=  0 ;
  82.  
  83.         for(auto[u, v ] : st[id]) {
  84.             if(union_set(u, v )) {
  85.                 cnt ++ ;
  86.             }
  87.         }
  88.         if(l == r ) {
  89.             res[l] = scc ;
  90.             FOR(ii, 1, cnt ) roll_back_dsu() ;
  91.             return ;
  92.         } else {
  93.             ll m = l + r >> 1;
  94.             get(id << 1, l, m) ;
  95.             get(id << 1 | 1,  m +1, r ) ;
  96.         }
  97.         FOR(ii, 1, cnt ) roll_back_dsu() ;
  98.     }
  99.  
  100.  
  101. } seg;
  102. //**Function**//
  103.  
  104. void init() {
  105.     memset(lab,  -1, sizeof lab ) ;
  106.     cin>>n >> q ;
  107.     scc = n ;
  108. }
  109.  
  110. void solve() {
  111. //    cout << " before " << endl ;
  112.     FOR(i, 1,  q ) {
  113.  
  114.         ll  x, y ;
  115.         char type ;
  116.         cin >> type ;
  117.         if(type == '?') que[i].t = 3;
  118.         else if(type == '+') {
  119.             cin >> x >> y ;
  120.             if(x > y ) swap(x, y ) ;
  121.             pair<ll,ll> key = {x, y } ;
  122.             mp[key].push(i) ;
  123.         } else {
  124.             cin >> x >> y ;
  125.             if(x > y ) swap(x, y ) ;
  126.             pair<ll,ll> key = {x, y } ;
  127.             ll pre = mp[key].top() ;
  128.             seg.update(1, 0, q, pre, i, key ) ;
  129.             mp[key].pop() ;
  130.         }
  131.     }
  132.     for(auto &it : mp ) {
  133.         while(!it.se.empty() ) {
  134.             seg.update(1, 0, q, it.se.top(), q, it.fi ) ;
  135.             it.se.pop() ;
  136.         }
  137.     }
  138.     seg.get(1, 0, q  ) ;
  139.     FOR(i, 1,  q ) if(que[i].t == 3 ) cout << res[i] << el ;
  140. }
  141.  
  142. _ROOT_ {
  143.     // freopen(NAME".inp" , "r" , stdin);
  144.     // freopen(NAME".out" , "w", stdout) ;
  145. //    ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
  146.     srand(time(nullptr)) ;
  147.     int t = 1; // cin >> t ;
  148.     while(t--) {
  149.         init();
  150.         solve();
  151.     }
  152.     return (0&0);
  153. }
  154.  
Success #stdin #stdout 0.01s 36092KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
Standard output is empty
https://ideone.com/iGzDnK
language:
C++14 (gcc 8.3)
created:
22 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!