P2391 白雪皑皑
题目大意
给定一个序列，\(m\)次染色，每次将一个区间内的点染色\(i\)，染过色的元素可覆盖，求\(m\)次染色后，每个元素的颜色。
思路
性质：如果暴力染色的话，肯定T飞，那我们就看看时间消耗在了哪里？每个元素可能被多次染色。于是我们找性质，可以发现，每个元素的颜色肯定是最后一次被染上的颜色，于是我们倒着染色，这样就可以保证每个元素第一次被染上的颜色就是答案。那我们依旧是遍历整个区间，看谁没被染色的话就染上吗？那样和暴力有啥区别呢？因为每次染色是一段连续的区间，我们是不是可以用并查集来维护序列联通性呢？
\(fa[i]\)表示\(i\)之前第一个没被染色的元素（包括自己）。
这样我们就可以在染色区间上跳跃着染色，避免了依次经过染色的点所消耗的时间。
因为每个元素只会被染色一次，所以时间复杂度就是\(O(n)\)。
代码
点击查看代码
#include<iostream>
#include<cstdio>
using namespace std;
inline int read(){
int w=0,f=1;char ch=getchar();
while(ch<'0'||ch>'9'){
if(ch=='-') f=-1;
ch=getchar();
}
while(ch>='0'&&ch<='9'){
w=w*10+ch-'0';
ch=getchar();
}
return w*f;
}
int n,m,p,q,fa[1000005],col[1000005];
int get(int x){
if(fa[x]==x) return x;
return fa[x]=get(fa[x]);
}
int main(){
n=read(),m=read(),p=read(),q=read();
for(int i=1;i<=n;i++) fa[i]=i;
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);
for(int j=r;j>=l;){
int t=get(j);
if(t==j){
col[j]=i;
fa[j]=get(j-1);
}
j=fa[j];
}
}
for(int i=1;i<=n;i++) cout<<col[i]<<"\n";
return 0;
}