本蒟蒻用并查集写的，大概就是用g[i]存下一个要染色的点（包括点i）

1.WA代码(j从l到r)

#include<bits/stdc++.h>
#define int long long
using namespace std;

int n, m, p, q, col[1010101], g[1010101];
//col[]是颜色
int find(int x){
	if(g[x] == x) return x;
	return g[x] = find(g[x]);
}

signed main(){
	scanf("%lld\n%lld\n%lld\n%lld", &n, &m, &p, &q);
	for(int i = 1; i <= n; i++){
		g[i] = i;
	}
	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);
		for(int j = l; j <= r;){ 
			int t = find(j); //找到没染色的 
            if(t == j){
            	col[t] = i;
				g[t] = find(t + 1);
			}
		    j = g[j];
		}
	}
	for(int i = 1; i <= n; i++){
		printf("%lld\n", col[i]);
	}
	return 0;
}

2.ACdaima(j从r到l)

#include<bits/stdc++.h>
#define int long long
using namespace std;

int n, m, p, q, col[1010101], g[1010101];

int find(int x){
	if(g[x] == x) return x;
	return g[x] = find(g[x]);
}

signed main(){
	scanf("%lld\n%lld\n%lld\n%lld", &n, &m, &p, &q);
	for(int i = 1; i <= n; i++){
		g[i] = i;
	}
	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);
//		cout << i << endl;
		for(int j = r; j >= l;){
			int t = find(j); //找到没染色的 
//			cout << t << " ";
            if(t == j){
            	col[t] = i;
//			if(t + 1 >= r) break;
				g[t] = find(t - 1);
			}
		    j = g[j];
			
		}
//		cout << endl;
	}
	for(int i = 1; i <= n; i++){
		printf("%lld\n", col[i]);
	}
	return 0;
}