P2391 白雪皑皑（并查集）

https://www.luogu.com.cn/problem/P2391

题目背景

“柴门闻犬吠，风雪夜归人”，冬天，不期而至。千里冰封，万里雪飘。空中刮起了鸭毛大雪。雪花纷纷，降落人间。 美能量星球（pty 在 spore 上的一个殖民地）上的人们被这美景所震撼。但是 pty 却不高兴，他不喜欢白色的世界，他觉得这样太单调了。所以他想对雪花进行染色，让世界变得多彩些。

题目描述

现在有 \(n\) 片雪花排成一列。 pty 要对雪花进行 \(m\) 次染色操作，第 \(i\) 次染色操作中，把第 \(((i\times p+q)\bmod n)+1\) 片雪花和第 \(((i\times q+p)\bmod n)+1\) 片雪花之间的雪花（包括端点）染成颜色 \(i\)。其中 \(p,q\) 是给定的两个正整数。他想知道最后 \(n\) 片雪花被染成了什么颜色。没有被染色输出 \(0\)。

输入格式

输入共四行，每行一个整数，分别为 \(n,m,p,q\)，意义如题中所述。

输出格式

输出共 \(n\) 行，每行一个整数，第 \(i\) 行表示第 \(i\) 片雪花的颜色。

样例 #1

样例输入 #1

4
3
2
4

样例输出 #1

2
2
3
0

提示

• 对于 \(20\%\) 的数据满足：\(n,m\leq 1000\)。
• 对于 \(40\%\) 的数据满足：\(n\leq 8000\)，\(m\leq 10^6\)。
• 对于 \(80\%\) 的数据满足：\(n\leq 5\times 10^5\)，\(m\leq 10^7\)。
• 对于 \(100\%\) 的数据满足：\(1\leq n\leq 10^6\)，\(1\leq m\leq 10^7\)。

保证 \(1\leq m\times p+q,m\times q+p\leq 2\times 10^9\)。

思路

前面已经染过的颜色会被最后染的颜色覆盖，所以倒着求解：如果当前染色区间存在没被染过的点就把他染上（最终颜色一定是当前染上的色）。并查集维护连通性：\(fa_i\) 表示 \(i\) 后第一个可操作的点。

Code

#include <bits/stdc++.h>

using namespace std;
const int N = 1e6 + 5, M = 1e7 + 5;
int n, m, p, q;
int fa[N], ans[N]; //fa[i]: i后第一个可操作的点

int find (int x) {
    if (x != fa[x])     fa[x] = find (fa[x]);
    return fa[x];
}

int main () {
    cin >> n >> m >> p >> q;
    for (int i = 1; i <= n; i++)    fa[i] = i;
    for (int i = m; i >= 1; i--) {
        int l = (i * p + q) % n + 1, r = (i * q + p) % n + 1;
        if (l > r)  swap (l, r);
        for (int j = r; j >= l; j = fa[j]) {
            int fj = find (j);
            if (fj == j)    ans[j] = i, fa[j] = find (j - 1);
        }
    }
    for (int i = 1; i <= n; i++) cout << ans[i] << endl;
}