并查集

$O(mlogn)$

C++ 代码

#include <cstdio>
#include <algorithm>
#include <cstring>

using namespace std;

const int N = 1e6 + 5;

int ans[N], f[N], n, m, p, q;

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

int main(){
    scanf("%d %d %d %d", &n, &m, &p, &q);

    // 为了防止越界, 多设置一个f[n + 1]
    // f[i]表示i的右边第一个没有被染色的馒头的下标
    for(int i = 1; i <= n + 1; i++) f[i] = i;

    // 由于以最后一次染的颜色为准, 因此需要倒序操作
    for(int i = m; i >= 1; i--){
        int d = (i * p + q) % n + 1, t = (i * q + p) % n + 1;
        int l = min(d, t), r = max(d, t);
        while(find(l) <= r){
            l = find(l);    // 指针移动到最近一个未被染色的馒头位置
            ans[l] = i;     // 染色
            f[l] = l + 1;   // 与下一个馒头连接
            }
        }
    for(int i = 1; i <= n; i++) printf("%d\n", ans[i]);
    return 0;
}