题目描述

CQF 十分喜欢吃馒头。

兴奋之下他一下子买了 N 个馒头请所有认识他的人吃。

但是 CQF 不喜欢白色，喜欢红色、黄色、绿色等鲜艳的颜色。

于是他把所有白色的馒头排成一列。

然后进行 M 次染色操作。

每个染色操作都是用一个神奇的刷子把连续的多个馒头染成特定的某种颜色。

一个馒头最终的颜色是最后一次染它的颜色。

如果一个馒头没有被染过色，那么它的颜色就是白色。

现在 CQF 已经定好了染色计划:在第 i 次染色操作中，把第 $(i×p+q)modN+1$ 个馒头和第$ (i×q+p)modN+1 $个馒头之间的馒头染成颜色 i，其中 p,q 是特定的两个正整数。

他想立即知道最后每个馒头的颜色。

你能帮他吗?

输入格式

第一行四个正整数 N,M,p,q。

输出格式

一共输出 N 行，第 i 行表示第 i 个馒头的最终颜色（如果最终颜色是白色就输出 0。

样例

输入
4 3 2 4
输出
2
2
3
0

算法1

并查集

根据题目描述： 一个馒头最终的颜色是最后一次染它的颜色，所以我们可以从后往前染色，这样第一次染色就是这个馒头最后的颜色

每个点一开始的父节点指向自己，代表自己还没有染色，我们并查集的f数组定义成从该点开始包括当前点向右，第一个未染色的点的坐标
当一个点被染色后，它的父节点指向右边第一个还未染色的点，那对每次染色找到一个区间内可以染色的点然后更新颜色以及f数组即可

时间复杂度

O(MlogN)
实际运行效率O(M)

C++ 代码

#include<bits/stdc++.h>

using namespace std;

const int N = 1e6+10;

int n,m,p,q;
int w[N];   // 记录每个馒头最终是哪个颜色
int f[N];

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

int main()
{

    cin>>n>>m>>p>>q;
    for(int i = 1; i<=n+1 ; ++i) f[i] = i;  // 这里要初始化到n+1, 数组f定义的严密性

    // 根据题目描述： 一个馒头最终的颜色是最后一次染它的颜色
    // 所以我们可以从后往前染色，这样第一次染色就是这个馒头最后的颜色
    typedef long long LL;
    for(int i = m; i>=1; i--){
        int l = ((LL)i*p+q)%n+1;
        int r = ((LL)i*q+p)%n+1;
        if(l>r) swap(l,r);

        int t = find(l);  // 找到当前这个区间内第一个可以被染色的馒头
        while(t <= r){
            w[t] = i;  // 更新颜色
            f[t] = t+1;  // 根据定义更新f数组
            t = find(t);  // 一直向右侧找
        }
    }
    for(int i = 1; i<=n ; ++i) printf("%d\n",w[i]);
    return 0;
}