[文章目录]
Description
他把所有白色的馒头排成一列。然后进行M次染色操作。每个染色操作都是用一个神奇的刷子把连续的多个馒头染成特定的某种颜色。一个馒头最终的颜色是最后一次染它的颜色。如果一个馒头没有被染过色，那么它的颜色就是白色。
现在小t已经定好了染色计划：在第i次染色操作中，把第(i×p + q)mod N + 1个馒头和第(i×q + p)mod N + 1个馒头之间的馒头染成颜色i，其中p，q是特定的两个正整数。他想立即知道最后每个馒头的颜色。
因为决定每只馒头的颜色的只有最后一次染色情况，所以我们倒序求解。不过，因为m与n巨大，所以我们就希望扫的时候直接掠过之前染过色的区间，所以就引入并查集，让每个区间中的点指向其右边第一个没染过色的点。然后进行染色。不过好像我并没有路径压缩就过了。
#include <cstdio>
#include <iostream>
#include <algorithm>
using namespace std;
int n,m,p,q;
int f[1001000],fa[1001000];
int main()
{
scanf("%d%d%d%d",&n,&m,&p,&q);
for(int i=m;i>=1;i--)
{
int k1=(i*p+q)%n+1;
int k2=(i*q+p)%n+1;
if(k1>k2)
swap(k1,k2);
k2++;
while(k1<k2)
{
if(!f[k1])
{
f[k1]=i;
fa[k1]=k2;
k1++;
}
else
k1=fa[k1];
}
}
for(int i=1;i<=n;i++)
printf("%d\n",f[i]);
return 0;
}