[題解]（并查集）luogu_P2391 白雪皚皚

今天被老師留的作業搞死了，全是裸的水題，難題就那麼兩道我還沒寫......，狗屎

---

1.倒序處理，每個點至多會被更新一次

2.所以要做的就是快速找到下一個不同顏色的點，

3.然而不知道怎麼就 想到用并查集維護 了？用雙向鏈錶不是更自然碼（雖然也可以）

4.其實并查集就是把相鄰的相同顏色的點并成一個，直接處理端點即可

#include<iostream>
#include<cstdio>
#include<cstring>
using namespace std;
const int maxn=1000010;
int n,m,p,q,fa[maxn],a[maxn];
int find(int x){
    if(fa[x]<0)return x;
    else return fa[x]=find(fa[x]);
}
int main()
{
    scanf("%d%d%d%d",&n,&m,&p,&q);
    memset(fa,-1,sizeof(fa));
    for(int i=m;i>=1;i--){
        int l=(i*p+q)%n+1,r=(i*q+p)%n+1;
        if(l>r)swap(l,r);
        l=find(l);
        while(l<=r)a[l]=i,fa[l]=l+1,l=find(l+1);//每次把l和l+1合併,一定是一樣的，因為l是左端點 
    }
    for(int i=1;i<=n;i++)printf("%d
",a[i]);
}