Acwing 3115. 疯狂的馒头 并查集维护区间覆盖

题目链接

用并查集维护$fa[i]$表示$i$右边(包括$i$)第一个没被覆盖的位置， 这种方法适用于每个点只被覆盖一次的情况

#include <iostream>
#include <cstdio>

int n, m, p, q;
int fa[1000006], c[1000006];

struct Unionfindset
{
    void Init()
    {
        for(int i = 1; i <= n + 1; i ++) fa[i] = i;
    }

    int Find(int x)
    {
        return fa[x] == x ? x : fa[x] = Find(fa[x]);
    }
} ufs;

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

    ufs.Init();

    for(int i = m; i; i --)
    {
        int a = ((i * q + p) % n) + 1, b = ((i * p + q) % n) + 1;

        int l = std:: min(a, b), r = std:: max(a, b);

        int now = ufs.Find(l);
        while(now <= r)
            c[now] = i, fa[now] = ufs.Find(now + 1), now = fa[now];
    }

    for(int i = 1; i <= n; i ++) printf("%d\n", c[i]);

    return 0;
}