并查集应用。

题干分析：

• 染色区间为：(i×p+q)modN+1 和 (i×q+p)modN+1 之间的馒头，因为不知道这两个数的大小，所以取这两个数中的小值为区间左边界，大值为区间右边界。

• 后面染色会覆盖前面的染色，所以染色顺序从后往前染，且被染过的馒头不会再次染色。

思路：

• 用数组ans保存每个馒头的颜色，初始时，各个值为0。

• 用数组f保存各个编号的父节点编号。当父节点是自己的时候，表示该馒头可以被染色。初始时，f[i] = i。

• 函数find(x):输入馒头编号，返回从编号为x的馒头开始，第一个可以被染色的馒头的编号。（并查集的find操作）

• 根据输入的 n, m, p, q, n 可以算出染色区间[l, r]。

• 找到第一个可以被染色的馒头：find(l)，记做x，如果编号小于等于r，该馒头染色:ans[x] = m，更新f[x] = find(x + 1);

• 接着找下一个可以被染上的馒头find(x)，如果编号小于等于r，该馒头染色:ans[x] = m，更新f[x] = find(x + 1);

• 重复上述步骤，直到能被染色的馒头编号大于 r。

• ans中保存的就是每个馒头的颜色。

#include<iostream>
#include <algorithm>
using namespace std;
const int N = 1000010;
int f[N];
int ans[N];
int find(int x)
{
    if (f[x] != x) f[x] = find(f[x]);
    return f[x];
}

int main()
{
    for (int i = 1; i <= N; i++) f[i] = i;
    int n;
    cin >> n;
    int m;
    cin >> m;
    int p, q;
    cin >> p >> q;
    while (m)
    {

        int x = (m * p + q) % n + 1;
        int y = (m * q + p) % n + 1;
        int l = min(x, y);
        int r = max(x, y);
        x = find(l);
        while (x <= r)
        {
            ans[x] = m;
            f[x] = find(x + 1);
            x = find(x);
        }
        m--;
    }
    for (int i = 1; i <= n; i++)
        printf("%d\n", ans[i]);
}