BZOJ 2054: 疯狂的馒头

Description

CQF十分喜欢吃馒头。兴奋之下他一下子买了N 个馒头请所有认识他的人吃。

但是CQF不喜欢白色，喜欢红色、黄色、绿色等鲜艳的颜色。于是他把所有白色的馒头排成一列。然后进行M 次染色操作。每个染色操作都是用一个神奇的刷子把连续的多个馒头染成特定的某种颜色。一个馒头最终的颜色是最后一次染它的颜色。如果一个馒头没有被染过色，那么它的颜色就是白色。现在CQF已经定好了染色计划：在第i次染色操作中，把第(i × p + q)mod N + 1个馒头和第(i × q + p)mod N + 1个馒头之间的馒头染成颜色i，其中p, q是特定的两个正整数。他想立即知道最后每个馒头的颜色。你能帮他吗？

Input

第一行四个正整数N，M，p，q

Output

一共输出N行，第i行表示第i个馒头的最终颜色（如果最终颜色是白色就输出0）。

Sample Input

4 3 2 4

Sample Output

HINT

在20%的数据中，1 ≤ N ≤ 1000，1 ≤ M ≤ 10000

在40%的数据中，1 ≤ N ≤ 10000，1 ≤ M ≤ 100000

在60%的数据中，1 ≤ N ≤ 50000，1 ≤ M ≤ 500000

在80%的数据中，1 ≤ N ≤ 300000，1 ≤ M ≤ 3000000

在100%的数据中，1 ≤ N ≤ 1000000，1 ≤ M ≤ 10000000

保证所以输入数据中1 ≤ M ∗ p + q, M ∗ q + p ≤ 231 − 1。

Solution

并查集

对于每个节点，f[i]为i点和i点右边第一个白馒头的位置。然后倒着染色，每次找到白馒头，把他染成对应的颜色即可。因为每个馒头都最多会被染色1次，因此复杂度就有保证了。

Code

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
#include <cstdio>
#include <algorithm>
using namespace std;
typedef long long LL;
const int INF = 1009999999;
int getint() {
    int r = 0, k = 1; char c = getchar();
    for (; '0' > c || c > '9'; c = getchar()) if (c == '-') k = -1;
    for (; '0' <= c && c <= '9'; c = getchar()) r = r * 10 - '0' + c;
    return r * k;
}
int ri[1000006], n, m, a[1000006], p, q, l, r, x;
int Find(int x) {
    if (ri[x] == x) return x;
    return ri[x] = Find(ri[x]);
}
int main() {
    n = getint(); m = getint(); p = getint(); q = getint();
    for (int i = 1; i <= n; ++i) ri[i] = i;
    ri[n+1] = n+1;
    for (int i = m; i >= 1; --i) {
        l = (i * p + q) % n + 1;
        r = (i * q + p) % n + 1;
        if (l > r) swap(l, r);
        x = Find(ri[r + 1]);
        for (int j = Find(l); j <= r; j = Find(j + 1)) {
            a[j] = i;
            ri[j] = x;
        }
    }
    for (int i = 1; i <= n; ++i)
        printf("%d\n", a[i]);
}