并查集维护线段连通

二分线段染色

#include <bits/stdc++.h>
using namespace std;
const int maxn = 1e6 + 6;
int n, m, p, q;
int col[maxn], fa[maxn];
int find(int x) {
    return fa[x] == x ? x : fa[x] = find(fa[x]);
}
bool merge(int x, int y) {
    x = find(x);
    y = find(y);
    if (x == y) return 0;
    fa[y] = x;
    return 1;
}
bool con(int x, int y) {
    return find(x) == find(y);
}
void print(int l, int r, int c) {
    if (l == r) {
        if (!col[l]) {
            col[l] = c;
            if (col[l + 1])
                merge(l, l + 1);
            if (col[l - 1])
                merge(l, l - 1);
        }
        return;
    }
    int mid = l + r >> 1;
    if (!con(l, r)) {
        print(l, mid, c);
        print(mid + 1, r, c);
    }
}
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;
        int r = (i * q + p) % n + 1;
        if (l > r) swap(l, r);
        if (con(1, n)) break;
        print(l, r, i);
    }
    for (int i = 1; i <= n; i++) {
        printf("%d\n", col[i]);
    }
}