BZOJ 2054 疯狂的馒头

题目大意

给你一堆馒头和一堆区间染色操作，请你输出操作结束后每个馒头的颜色。

这题讲过……

因为染色有“染完还可以被覆盖，每一个馒头只有最终状态的颜色会表现出来”这一特点，再结合超大的数据范围，基本确定O(N)。 之后我们可以考虑并查集加速暴力，没染色的fa[i]=i,染过色的fa[i]=i+1，结合路径压缩之后我们得到了非常优异的时间复杂度，直接过了。

#include <cstdio>
#include <algorithm>
using namespace std;
int n,m,p,q,ans[1000010],fa[1000010],x,y,cnt;
int unifind(int tx)
{
    return fa[tx]==tx?tx:fa[tx]=unifind(fa[tx]);
}
int main()
{
    scanf("%d%d%d%d",&n,&m,&p,&q);
    for(int i=1;i<=n+1;++i) fa[i]=i;
    for(int i=m;i;i--)
    {
        x=((i*p+q)%n)+1;
        y=((i*q+p)%n)+1;
        if(x>y) swap(x,y);
        for(int j=unifind(x);j<=y;j=unifind(j))
        {
            fa[j]=j+1,ans[j]=i,++cnt;
            if(cnt==n) break;
        }
        if(cnt==n) break;
    }
    for(int i=1;i<=n;++i) printf("%d\n",ans[i]);
    return 0;
}