[luogu P2391] 白雪皑皑
题目背景
“柴门闻犬吠,风雪夜归人”,冬天,不期而至。千里冰封,万里雪飘。空中刮起了鸭毛大雪。雪花纷纷,降落人间。 美能量星球(pty 在 spore 上的一个殖民地)上的人们被这美景所震撼。但是 pty 却不高兴,他不喜欢白色的世界,他觉得这样太单调了。所以他想对雪花进行染色,让世界变得多彩些。
题目描述
现在有 N 片雪花排成一列。 Pty 要对雪花进行 M 次染色操作,第 i次染色操作中,把第(i*p+q)%N+1 片雪花和第(i*q+p)%N+1 片雪花之间的雪花(包括端点)染成颜色 i。其中 p,q 是给定的两个正整数。他想知道最后 N 片雪花被染成了什么颜色。
输入输出格式
输入格式:
包含 4 行:
N M p q 意义如题中所述。
输出格式:
包含 N 行:
第 i 行表示第 i 片雪花被染成的颜色 c
输入输出样例
说明
20%的数据满足:1<=n,m<=1000
40%的数据满足:1<=n<=8000,1<=m<=1000000
80%的数据满足:1<=n<=500000,1<=m<=10000000
100%的数据满足:1<=n<=1000000,1<=m<=10000000
保证 1<=M*p+q,M*q+p<=2*10^9
脑子都不好使了。。。并查集都用不来了。
对于这一题,我们可以把原问题转为做m次修改。
每一次修改,在一个区间内,把没有修改过的位置染上色(即修改)。
然后,最后输出每一个位置分别是哪一种颜色(即哪次修改,也可能为0,表示没有修改)。
妙用并查集,有点链表的味道,用fa[i]表示1~i里面,离i最近的没有被修改过的位置。
然后,对于一次修改,把当前位置修改好了就修改fa[i],一直到修改好为止(或是修改到0)。
由于每个位置最多被修改1次,所以复杂度是O(n)的。最多乘上一个并查集常数。
有个地方还需要探讨一下——就是路径压缩的问题。
对于这题,路径压缩之后有没有影响?
不存在的。我们可以吧点于点的关系看做是树,森林。
那么,事实上,只有根节点才没有被修改过,其他点都是已经修改过的,所以无论关系怎么变化,都不会有影响。
当然,运用并查集就是为了增快查询速度,而且路径压缩是关键。
注意,在更新fa[i]时,直接取i-1或fa[i-1]或get(i-1)就好,因为i这个位置被访问到当且仅当它第一次被更新到。
那么这样,根据定义,fa[i]就是get(i-1)了。
code:
#pragma GCC optimize(2) #include<cstdio> #include<cstring> #include<algorithm> typedef long long LL; namespace fastIO { inline int read() { ,f=; char ch=getchar(); ') { if (ch=='-') f=-f; ch=getchar(); } ') { x=(x<<)+(x<<)+ch-'; ch=getchar(); } return x*f; } ]; inline void write(int x) { ) { putchar('); return; } ) { x=-x; putchar('-'); } ; x; x/=) w[++cnt]=x%; ); } inline void newline() { putchar('\n'); } } namespace OJ{ void Online_Judge() { #ifndef ONLINE_JUDGE freopen("in.txt","r",stdin); freopen("out.txt","w",stdout); #endif } } ; int n,m,p,q,fa[N],cov[N]; inline int get(int x) { return fa[x]==x?x:fa[x]=get(fa[x]); } int main() { OJ::Online_Judge(); using namespace fastIO; n=read(),m=read(),p=read(),q=read(); ; i<=n; ++i) { cov[i]=; fa[i]=i; } int l,r; for (int i=m; i; --i) { l=(i*p+q)%n+,r=(i*q+p)%n+; if (l>r) std::swap(l,r); for (r=get(r); l<=r; r=get(r)) { cov[r]=i; fa[r]=r-; } } ; i<=n; ++i) { write(cov[i]); newline(); } ; }