Codefores CROC D
問題
方針
いつもの区間クエリの平方分割。
ソースコード
const int SZ = 500; int n, m, q; int a[10000], b[10000]; int l[20000], r[20000], ans[20000]; int p[500], p2[500]; inline int root(int *p, int x){ if(p[x] == x) return x; return p[x] = root(p, p[x]); } inline void merge(int *p, int a, int b){ a = root(p, a); b = root(p, b); if(a != b) p[a] = b; } int main(){ scanf("%d%d", &n, &m); rep(i, m) scanf("%d%d", a + i, b + i), a[i]--, b[i]--; scanf("%d", &q); vector<pi> qs[SZ]; rep(i, q){ scanf("%d%d", l + i, r + i); l[i]--; qs[l[i] / SZ].pb(mp(r[i], i)); } rep(it, SZ){ sort(all(qs[it]), greater<pi>()); rep(i, n) p2[i] = i; rep(i, min(m, it * SZ)) merge(p2, a[i], b[i]); int rr = m; rep(i, qs[it].size()){ while(rr > qs[it][i].first){ rr--; merge(p2, a[rr], b[rr]); } rep(j, n) p[j] = p2[j]; for(int j = it * SZ; j < l[qs[it][i].second]; j++) merge(p, a[j], b[j]); int cnt = 0; bool use[500] = {}; rep(j, n) if(!use[root(p, j)]) use[root(p, j)] = 1, cnt++; ans[qs[it][i].second] = cnt; } } rep(i, q) printf("%d\n", ans[i]); return 0; }