arujbansal

Untitled

Sep 22nd, 2021
774
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  1. #include <bits/stdc++.h>
  2.  
  3. using namespace std;
  4.  
  5. void dbg_out() { cerr << endl; }
  6. template<typename Head, typename... Tail>
  7. void dbg_out(Head H, Tail... T) { cerr << ' ' << H; dbg_out(T...); }
  8. #define dbg(...) cerr << "(" << #__VA_ARGS__ << "):", dbg_out(__VA_ARGS__)
  9.  
  10. #define rng_init mt19937 rng(chrono::steady_clock::now().time_since_epoch().count())
  11. #define rng_seed(x) mt19937 rng(x)
  12. #define all(x) (x).begin(), (x).end()
  13. #define sz(x) (int) (x).size()
  14. // #define int long long
  15.  
  16. struct UFDS {
  17.     int n, components;
  18.     vector<int> info;
  19.    
  20.     UFDS(int _n = 0) { init(_n); }
  21.  
  22.     void init(int _n) {
  23.         n = _n;
  24.         components = n;
  25.         info.assign(n, -1);
  26.     }
  27.  
  28.     int find(int x) { return info[x] < 0 ? x : info[x] = find(info[x]); }
  29.  
  30.     bool unite(int u, int v) {
  31.         u = find(u), v = find(v);
  32.         if (u == v) return false;
  33.  
  34.         if (info[u] > info[v]) swap(u, v);
  35.         info[u] += info[v];
  36.         info[v] = u;
  37.         components--;
  38.  
  39.         return true;
  40.     }
  41.  
  42.     bool connected(int u, int v) { return find(u) == find(v); }
  43.  
  44.     int component_count() { return components; }
  45. };
  46.  
  47. const int MXN = 1e5 + 5, INF = 1e9 + 5;
  48.  
  49. void solve() {
  50.     int N, M, Q;
  51.     cin >> N >> M >> Q;
  52.  
  53.     vector<pair<int, int>> edges(M);
  54.     for (int i = 0; i < M; i++) {
  55.         cin >> edges[i].first >> edges[i].second;
  56.         edges[i].first--, edges[i].second--;
  57.     }
  58.  
  59.     vector<int> block(M);
  60.     int block_size = sqrt(M);
  61.  
  62.     for (int i = 0; i < M; i++)
  63.         block[i] = i / block_size;
  64.  
  65.     vector<pair<int, int>> queries[M];
  66.     for (int i = 0; i < Q; i++) {
  67.         int l, r;
  68.         cin >> l >> r;
  69.         l--, r--;
  70.  
  71.         queries[r].emplace_back(l, i);
  72.     }
  73.  
  74.     vector<int> ans(Q);
  75.  
  76.     vector<UFDS> ufds(block_size + 5, UFDS(N));
  77.     UFDS temp(N);
  78.  
  79.     vector<int> last(N, -1), last_rem;
  80.  
  81.     for (int i = 0; i < M; i++) {
  82.         for (int cur_block = block[i]; cur_block >= 0; cur_block--)
  83.             ufds[cur_block].unite(edges[i].first, edges[i].second);
  84.  
  85.         for (int q = 0; q < sz(queries[i]); q++) {
  86.             int l = queries[i][q].first, idx = queries[i][q].second;
  87.  
  88.             if (block[l] == block[i]) {
  89.                 for (int j = l; j <= i; j++)
  90.                     temp.unite(edges[j].first, edges[j].second);
  91.                
  92.                 ans[idx] = temp.component_count();
  93.                
  94.                 for (int j = l; j <= i; j++) {
  95.                     temp.info[edges[j].first] = -1;
  96.                     temp.info[edges[j].second] = -1;
  97.                 }
  98.  
  99.                 temp.components = N;
  100.                
  101.                 continue;
  102.             }
  103.  
  104.             ans[idx] = ufds[block[l] + 1].component_count();
  105.  
  106.             for (int j = l; block[l] == block[j] && j <= i; j++) {
  107.                 int u = edges[j].first, v = edges[j].second;
  108.                 int p1 = ufds[block[l] + 1].find(u), p2 = ufds[block[l] + 1].find(v);
  109.  
  110.                 if (last[p1] > -1) temp.unite(u, last[p1]);
  111.                 if (last[p2] > -1) temp.unite(v, last[p2]);
  112.  
  113.                 last[p1] = u;
  114.                 last[p2] = v;
  115.  
  116.                 last_rem.push_back(p1);
  117.                 last_rem.push_back(p2);
  118.             }
  119.  
  120.             for (int j = l; block[l] == block[j] && j <= i; j++) {
  121.                 int u = edges[j].first, v = edges[j].second;
  122.                 ans[idx] -= temp.unite(u, v) && !ufds[block[l] + 1].connected(u, v);
  123.             }
  124.  
  125.             for (int j = l; block[l] == block[j] && j <= i; j++)
  126.                 temp.info[edges[j].first] = temp.info[edges[j].second] = -1;
  127.  
  128.             for (const auto &x : last_rem)
  129.                 last[x] = -1;
  130.  
  131.             last_rem.clear();
  132.  
  133.             temp.components = N;
  134.         }
  135.     }
  136.  
  137.     for (const auto &x : ans)
  138.         cout << x << "\n";
  139. }
  140.  
  141. signed main() {
  142.     ios_base::sync_with_stdio(false);
  143.     cin.tie(nullptr);
  144.  
  145.     int TC = 1;
  146.     cin >> TC;
  147.     while (TC--) solve();
  148. }
RAW Paste Data