学oi看这个世界都是反着的

懵逼的 题目

扯淡的 题解

我们发现这玩意是后面覆盖前面的…那我们可以从后向前染

然后我们发现一个馒头被染色之后就不会再被染色

我们可以用类似并查集上找LCA的方法, 走过的点都合并起来, 然后就没了

沙茶的 代码

/**************************************************************
    Problem: 2054
    User: Cansult
    Language: C++
    Result: Accepted
    Time:2268 ms
    Memory:9100 kb
****************************************************************/

#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
#define MAXN (1000000 + 5)
#define pii pair<int, int>
using namespace std;
int n, m, p, q, fa[MAXN], col[MAXN];
void solve(int le, int ri, int dqc)
{
    while (ri >= le)
    {
        int bkri = ri;
        if (!col[ri])
            col[ri] = dqc;
        ri = fa[ri];
        fa[bkri] = fa[le];
    }
}
int main()
{
    scanf("%d%d%d%d", &n, &m, &p, &q);
    for (int i = 1; i <= n; i++) fa[i] = i - 1;
    for (int i = m; i >= 1; i--)
        solve(min((i * p + q) % n + 1, (i * q + p) % n + 1), max((i * p + q) % n + 1, (i * q + p) % n + 1), i);
    for (int i = 1; i <= n; i++)
        printf("%d\n", col[i]);
    return 0;
}

By 联赛钦定爆零的 Cansult