【題解】Codeforces EDU Course-2 Lesson-7-3 B. Number of Connected Components on Segments

#include <iostream>
#include <vector>
#include <algorithm>
#include <cmath>
using namespace std;
 
int n, m, Q, k, x[50005], y[50005], p[50005], ans[50005], dep[50005];
vector <pair<int, pair<int, int> > > q[225];
 
bool cmp(pair<int, pair<int, int> > x, pair<int, pair<int, int> > y){
    if (x.second.first/k != y.second.first/k) return x.second.first/k < y.second.first/k;
    else return x.second.second < y.second.second;
}
int f(int x){
    if (p[x] == x) return x;
    return f(p[x]);
}
 
int main() {
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cin >> n >> m;
    k = sqrt(m);
    for (int i = 1; i <= m; i++){
        cin >> x[i] >> y[i];
    }
    cin >> Q;
    for (int i = 0, c, d; i < Q; i++){
        cin >> c >> d;
        q[c/k].push_back({i, {c, d}});
    }
    for (int i = 0; i < 225; i++){
        for (int j = 1; j <= n; j++){
            p[j] = j;
            dep[j] = 1;
        }
        int cnt = n;
        sort(q[i].begin(), q[i].end(), cmp);
        int mid = (i+1)*k, r = (i+1)*k;
        for (auto j:q[i]){
            if (j.second.second < mid){
                vector <pair<int, int> > v;
                for (int l = j.second.first; l <= j.second.second; l++){
                    int c = f(x[l]), d = f(y[l]);
                    if (c != d){
                        if (dep[c] > dep[d]) swap(c, d);
                        v.push_back({c, dep[d]});
                        p[c] = d;
                        dep[d] = max(dep[d], dep[c]+1);
                        cnt--;
                    }
                }
                ans[j.first] = cnt;
                reverse(v.begin(), v.end());
                for (auto l:v){
                    cnt++;
                    dep[p[l.first]] = l.second;
                    p[l.first] = l.first;
                }
                continue;
            }
            while (r <= j.second.second){
                int c = f(x[r]), d = f(y[r]);
                if (c != d){
                    if (dep[c] > dep[d]) swap(c, d);
                    p[c] = d;
                    dep[d] = max(dep[d], dep[c]+1);
                    cnt--;
                }
                r++;
            }
            vector <pair<int, int> > v;
            for (int l = mid-1; l >= j.second.first; l--){
                int c = f(x[l]), d = f(y[l]);
                if (c != d){
                    if (dep[c] > dep[d]) swap(c, d);
                    v.push_back({c, dep[d]});
                    p[c] = d;
                    dep[d] = max(dep[d], dep[c]+1);
                    cnt--;
                }
            }
            ans[j.first] = cnt;
            reverse(v.begin(), v.end());
            for (auto l:v){
                cnt++;
                dep[p[l.first]] = l.second;
                p[l.first] = l.first;
            }
        }
    }
    for (int i = 0; i < Q; i++){
        cout << ans[i] << "\n";
    }
}