Luogu P2391 白雪皑皑

题目描述

https://www.luogu.com.cn/problem/P2391

Solution

正难则反

我们考虑如果将染色过程反过来，那么每次需要的操作就是将操作区间中还没染色的点染色

所以我们直接用并查集维护连通性即可

#include<iostream>
#include<cstdio>
#include<cstring>
#define maxn 1000010
using namespace std;

int n, m, p, q, col[maxn], f[maxn];

int find(int x) { return f[x] ? f[x] = find(f[x]) : x; }
int main() {
	cin >> n >> m >> p >> q;
	for(int i = m; i >= 1; --i) {
		int l = (i * p + q) % n + 1, r = (i * q + p) % n + 1;
		if(l > r) swap(l, r); l = find(l);
		while (l <= r) col[l] = i, l = f[l] = find(l + 1);
	}
	for(int i = 1; i <= n; ++i) printf("%d\n", col[i]);
	return 0; 
}