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;
}