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

---

?

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\n",a[i]); }

?

轉載于:https://www.cnblogs.com/superminivan/p/10720358.html

總結

以上是生活随笔為你收集整理的[題解]（并查集）luogu_P2391 白雪皚皚的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。