题目大意：给定一个序列，多次将某个区间染成某种颜色，求最后每个点是什么颜色
m<=1000W，线段树肯定T
由于对每个点起作用的染色只有最后一次，因此倒着做，如果一个点已经被染色，就在并查集中将这个点连向右面那个
这样每个点只会被染色一次，，时间复杂度O(n+m)
#include <cstdio>#include <cstring>#include <iostream>#include <algorithm>#define M 1001001using 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;}
当你成功得意的时候，最重要的是瞧得起别人。
