非常妙的构造题（妙到甚至没想到）
首先就是发现肯定是需要O(n)的算法
我们会发现倒着找出来的那一次就是馒头最后染色的次数
然后难点就在于如何保证每个馒头只需要被访问一次
答案是并查集
并查集记录着这个数右边第一个没有被染色过的馒头
感觉和noip2021年的那个第一题有异曲同工之妙，但是这个要难想一些
#include<bits/stdc++.h>
#define for1(i,a,b) for(int i = a;i<=b;i++)
#define ll long long
#define mp(a,b) make_pair(a,b)
using namespace std;
int n,m,p,q,cnt;
int fa[1000005],vis[1000005];
int gf(int x)
{
if(fa[x]==x) return x;
return fa[x]=gf(fa[x]);
}
int main()
{
scanf("%d%d%d%d",&n,&m,&p,&q);
for1(i,1,n)fa[i]=i;
fa[n+1]=n+1;
for(int i=m;i&&cnt<n;i--)
{
int x=(i*p+q)%n+1,y=(i*q+p)%n+1;
if(x>y)swap(x,y);
int ji=gf(x);
while(ji<=y&&cnt<n)
{
vis[ji]=i,++cnt;
fa[ji]=ji+1;
if(vis[ji]) ji=gf(ji);
}
}
for1(i,1,n) printf("%d\n",vis[i]);
return 0;
}