题目大意：给定一个序列，多次将某个区间染成某种颜色，求最后每个点是什么颜色
m<=1000W，线段树肯定T
由于对每个点起作用的染色只有最后一次，因此倒着做，如果一个点已经被染色，就在并查集中将这个点连向右面那个
这样每个点只会被染色一次，时间复杂度O(n+m)
#include#include #include #include #define M 1001001 using namespace std; int n,m,p,q; int a[M]; namespace Union_Find_Set{ int fa[M]; int Find(int x) { if(!fa[x]||fa[x]==x) return fa[x]=x; return fa[x]=Find(fa[x]); } } int main() { using namespace Union_Find_Set; int i,j; cin>>n>>m>>p>>q; for(i=m;i;i--) { int x=((long long)i*p+q)%n+1; int y=((long long)i*q+p)%n+1; if(x>y) swap(x,y); for(j=Find(x);j<=y;j=Find(j)) a[j]=i,fa[j]=j+1; } for(i=1;i<=n;i++) printf("%d\n",a[i]); return 0; }