Miku

显然思路是倒着扫，倒着染。

然而这样有一个问题，这样做，那么对于已经染色的区间是不需要重新染色的，

但是遍历的时候可以找到已染色区间的一个端点，另一个在哪？

用并查集解决

fa[x]为x右边第一个没染色的端点

然后就O（N）解决了

提示：n+1个点也要初始化，因为只要n点被染色，那么一定指向n+1，如果不初始化

fa[n+1]=0，那么就可以愉快的爆栈==15分了

#include<iostream>
#include<cstdio> 
#include<algorithm>
using namespace std;
int fa[1000001];
int ans[1000001];
int find(int x){
    if(fa[x]==x)
    return x;
    return fa[x]=find(fa[x]);
}
int n,m,p,q;
int u,v;
void deal(int l,int r,int c){
    for(int i=l;i<=r;){
        u=find(i);
        if(u<=r){
        ans[u]=c;
        fa[u]=r+1;
        i=u+1;
        }else{
            return ;
        }
    }
}
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>=1;--i){
        u=(i*p+q)%n+1;
        v=(i*q+p)%n+1;
        if(u>v)
        swap(u,v);
        deal(u,v,i);
    }
    for(int i=1;i<=n;++i){
        cout<<ans[i]<<endl;
    }
    return 0;
}