AcWing 3115. 疯狂的馒头

Posted on Edited on In 
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
#include <iostream>
using namespace std;
const int N = 1e6 + 10;
int n, m, p, q, f[N], color[N];
int find(int x) {
    if (f[x] != x) f[x] = find(f[x]);
    return f[x];
}
int main() {
    scanf("%d%d%d%d", &n, &m, &p, &q);
    for (int i = 1; i <= n + 1; ++i) f[i] = i;
    for (int i = m; i > 0; --i) {
        int l = (i * p + q) % n + 1,
            r = (i * q + p) % n + 1;
        if (l > r) swap(l, r);
        int pa = find(l);
        while (pa <= r) {
            color[pa] = i;
            f[pa] = find(pa + 1);
            pa = find(pa);
        }
    }
    for (int i = 1; i <= n; ++i) printf("%d\n", color[i]);
    return 0;
}
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
34
35
36
37
38
#include <iostream>
using namespace std;
const int N = 1e6 + 10;
struct Node {
    int l, r, v;
} t[N << 2];
int n, m, p, q;
void build(int u, int l, int r) {
    t[u] = {l, r, 0};
    if (l == r) return;
    int mid = l + r >> 1;
    build(u << 1, l, mid), build(u << 1 | 1, mid + 1, r);
}
void update(int u, int l, int r, int v) {
    if (t[u].v) return;
    if (t[u].l == t[u].r) t[u].v = v;
    else {
        int mid = t[u].l + t[u].r >> 1;
        if (l <= mid) update(u << 1, l, r, v);
        if (r > mid) update(u << 1 | 1, l, r, v);
        if (t[u << 1].v && t[u << 1 | 1].v) t[u].v = true;
    }
}
void output(int u) {
    if (t[u].l == t[u].r) printf("%d\n", t[u].v);
    else output(u << 1), output(u << 1 | 1);
}
int main() {
    scanf("%d%d%d%d", &n, &m, &p, &q);
    build(1, 1, n);
    for (int i = m; i; --i) {
        int l = (i * p + q) % n + 1, r = (i * q + p) % n + 1;
        if (l > r) swap(l, r);
        update(1, l, r, i);
    }
    output(1);
    return 0;
}