BZOJ 2054 瘋狂的饅頭 並查集

BZOJ 2054 瘋狂的饅頭 並查集

題目大意：給定一個序列，多次將某個區間染成某種顏色，求最後每個點是什麼顏色

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;
}