https://darkbzoj.tk/problem/2054
nle 10^6,mle 10^7
可以用线段树来暴力维护，而且数据也构造不了，应该是能过的
可以从后往前维护颜色，这样一个区间只要有颜色了就不在打标记，省了一部分时间
正解是并查集，还是从后往前考虑，将已经被染色的区间缩成一个点，它们的根是区间右端点的右边一个点
然后每次跳到根，把根染上色，再把根的父亲置为它右边一个点的根
#include<cstdio>
#include<algorithm>
#include<iostream>
#include<cmath>
#include<map>
#include<iomanip>
#include<cstring>
#define reg register
#define EN std::puts("")
#define LL long long
inline int read(){
register int x=0;register int y=1;
register char c=std::getchar();
while(c<'0'||c>'9'){if(c=='-') y=0;c=std::getchar();}
while(c>='0'&&c<='9'){x=x*10+(c^48);c=std::getchar();}
return y?x:-x;
}
int n,m;
int color[1000005],fa[1000005];
inline int find(int k){
return fa[k]==k?k:fa[k]=find(fa[k]);
}
int main(){
n=read();m=read();int p=read(),q=read();
for(reg int i=1;i<=n;i++) fa[i]=i;
fa[n+1]=n+1;
for(reg int l,r,i=m;i;i--){
l=(i*p+q)%n+1;r=(i*q+p)%n+1;
if(l>r) l^=r,r^=l,l^=r;
for(reg int j=find(l);j<=r;j=find(j+1)) color[j]=i,fa[j]=find(j+1);
}
for(reg int i=1;i<=n;i++) printf("%d
",color[i]);
return 0;
}