fork download
copy 
  1. #include <bits/stdc++.h>
  2. #define ll long long
  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 1000001
  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.  
  25. ll n, q, scc, m  ;
  26. ll res[MAXN] ;
  27. ll arr[MAXN];
  28. pair<ll,ll> edge[MAXN] ;
  29. ll lab[MAXN] ;
  30.  
  31. struct Data {
  32.     ll u, sz ;
  33. };
  34. stack<Data> his ;
  35. struct Query {
  36.     ll l, r, id ;
  37.     bool operator < (const Query & other ) const {
  38.         ll blA= l / BLOCK_SIZE, blB = other.l / BLOCK_SIZE ;
  39.         if(blA == blB) return r < other.r;
  40.         return blA < blB ;
  41.     }
  42. };
  43. vector<Query > que ;
  44. void reset() {
  45.     FOR(i, 0, n ) lab[i] = -1 ;
  46.     while(!his.empty()) his.pop() ;
  47.     scc = n ;
  48. }
  49.  
  50. ll find_set(ll a ) {
  51.     return lab[a] < 0 ? a : find_set(lab[a])  ;
  52. }
  53. void roll_back() {
  54.     scc += his.size() / 2;
  55.     while(!his.empty() ) {
  56.         Data u = his.top() ;
  57.         his.pop() ;
  58.         lab[u.u] = u.sz ;
  59.     }
  60. }
  61. bool union_set(ll u, ll v, ll snapshot ) {
  62.     u = find_set(u) ;
  63.     v = find_set(v) ;
  64.     if(u == v ) return false ;
  65.     if(lab[u] > lab[v]) swap(u, v ) ;
  66.     if(snapshot ) his.push({u, lab[u] }) ;
  67.     if(snapshot ) his.push({v, lab[v] }) ;
  68.     lab[u] += lab[v] ;
  69.     lab[v]=  u ;
  70.     scc -- ;
  71.     return true ;
  72. }
  73. void init() {
  74.     cin>> n >> m  ;
  75.     FOR(i, 1, m ) cin >> edge[i].fi >> edge[i].se ;
  76.     cin >> q;
  77.     FOR(i, 1, q ) {
  78.         ll l, r, id ;
  79.         cin >> l >> r;
  80.         que.push_back({l, r,i });
  81.     }
  82. }
  83.  
  84. void solve() {
  85.  
  86.     sort(que.begin(), que.end() ) ;
  87.     ll curBlock = -1 ;
  88.     ll curR  = - 1;
  89.     for(auto [l, r, id ] : que ) {
  90.         ll block = l / BLOCK_SIZE ;
  91.         if(block != curBlock ) {
  92.             reset() ;
  93.             curBlock= block ;
  94.             curR = (block + 1) * BLOCK_SIZE ;
  95.         }
  96.         while(curR <= r ) union_set(edge[curR].fi, edge[curR].se, 0 ), curR ++  ;
  97.         ll EndBlockL = min( {  (block + 1 ) * BLOCK_SIZE - 1 , m, r } )  ;
  98. //        cout << l << " " << EndBlockL << " " << id  << el ;
  99.         FOR(i, l,  EndBlockL) union_set(edge[i].fi, edge[i].se, 1 ) ;
  100.         res[id] = scc ;
  101.         roll_back() ;
  102.     }
  103.     FOR(i, 1,  q ) cout << res[i] << el ;
  104. }
  105.  
  106. _ROOT_ {
  107.     // freopen(NAME".inp" , "r" , stdin);
  108.     // freopen(NAME".out" , "w", stdout) ;
  109.     ios_base::sync_with_stdio(0);
  110.     cin.tie(0);
  111.     cout.tie(0);
  112.     srand(time(nullptr)) ;
  113.     int t = 1; // cin >> t ;
  114.     while(t--) {
  115.         init();
  116.         solve();
  117.     }
  118.     return (0&0);
  119. }
  120.  
Success #stdin #stdout 0s 5320KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
Standard output is empty
https://ideone.com/zktLmN
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!