BZOJ.疯狂的馒头

题目

算法标签: 并查集区间染色, 线段树剪枝, 线段树延迟标记

思路

因为每个馒头的颜色取决于最后的染色情况, 因此可以倒序向前进行染色每次将区间染为 $i$

并查集区间染色代码

#include <iostream>
#include <algorithm>
#include <cstring>

using namespace std;

const int N = 1e6 + 10, M = 1e7 + 10;

int n, m, p, q;
int fa[N], ans[N];

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

int main() {
   
    ios::sync_with_stdio(false);
    cin.tie(0), cout.tie(0);

    cin >> n >> m >> p >> q;
    for (int i = 0; i <= n + 1; ++i) fa[i] = i;

    for (int i = m; i >= 1; --i) {
   
        int u = (i * p + q) % n + 1;
        int v = (i * q + p) % n + 1;
        int l = min(u, v), r = max(u, v);

        int idx = find(l);
        while (idx <= r) {
   
            ans[idx] = i;
            fa[idx] = find(idx + 1);
            idx = find(idx);
        }
    }

    for (int i = 1; i <= n; ++i) cout << ans[i] << "\n";

    return 0;
}

线段树倒着推代码

因为倒着推, 线段树只需要记录当前区间颜色即可, 因为是从后向前推, 因此当遇到当前区间已经被染色, 直接返回,. 也就是剪枝操作, 线段树模拟, 时间复杂度 $O(m\log n)$ , 在超时的边缘, 但是因为有剪枝, 可以通过

#include <iostream>
#include <algorithm>
#include <cstring>

using namespace std;

const int N = 1e6 + 10;

int n, m, p, q;
struct Node {
   
    int l, r, val;
} tr[N << 2];

void push_up(int u) {
   
    if (tr[u << 1].val && tr[u << 1 | 1].val) tr[u].val = true;
}

void build(int u, int l, int r) {
   
    tr[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 modify(int u, int l, int r, int v) {
   
    if (tr[u].val) return;
    if (tr[u].l == tr[u].r) tr[u].val = v;
    else {
   
        int mid = tr[u].l + tr[u].r >> 1;
        if (l <= mid) modify(u << 1, l, r, v);
        if (r > mid) modify(u << 1 | 1, l, r, v);
        push_up(u);
    }
}

void query(int u) {
   
    if (tr[u].l == tr[u].r) {
   
        cout << tr[u].val << "\n";
        return;
    }
    query(u << 1);
    query(u << 1 | 1);
}

int main() {
   
    ios::sync_with_stdio(false);
    cin.tie(0), cout.tie(0);

    cin >> n >> m >> p >> q;

    build(1, 1, n);

    for (int i = m; i >= 1; --i) {
   
        int u = (i * p + q) % n + 1;
        int v = (i * q + p) % n + 1;
        if (u > v) swap(u, v);
        modify(1, u, v, i);
    }

    query(1);

    return 0;
}

线段树正着推代码

因为正着推涉及到区间修改, 因此需要维护一个延迟标记, 常数会更大一些, 无法通过, 但是逻辑是正确的

#include <iostream>
#include <algorithm>
#include <cstring>

using namespace std;

const int N = 1e6 + 10;

int n, m, p, q;
struct Node {
   
    int l, r, val, flag;
} tr[N << 2];

void push_up(int u) {
   
    if (tr[u << 1].val == tr[u << 1 | 1].val) tr[u].val = tr[u << 1].val;
    else tr[u].val = -1;
}

void push_down(int u) {
   
    if (tr[u].flag) {
   
        Node &ls = tr[u << 1], &rs = tr[u << 1 | 1];
        ls.val = tr[u].flag;
        ls.flag = tr[u].flag;
        rs.val = tr[u].flag;
        rs.flag = tr[u].flag;
        tr[u].flag = 0;
    }
}

void build(int u, int l, int r) {
   
    tr[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);
    push_up(u);
}

void modify(int u, int ql, int qr, int val) {
   
    if (tr[u].l >= ql && tr[u].r <= qr) {
   
        tr[u].val = val;
        tr[u].flag = val;
        return;
    }

    push_down(u);
    int mid = tr[u].l + tr[u].r >> 1;
    if (ql <= mid) modify(u << 1, ql, qr, val);
    if (qr > mid) modify(u << 1 | 1, ql, qr, val);
    push_up(u);
}

int query(int u, int k) {
   
    if (k >= tr[u].l && k <= tr[u].r && tr[u].val != -1) return tr[u].val;
    int mid = tr[u].l + tr[u].r >> 1;
    push_down(u);
    if (k <= mid) return query(u << 1, k);
    return query(u << 1 | 1, k);
}

int main() {
   
    ios::sync_with_stdio(false);
    cin.tie(0), cout.tie(0);

    cin >> n >> m >> p >> q;
    build(1, 1, n);

    for (int i = 1; i <= m; ++i) {
   
        int u = (i * p + q) % n + 1;
        int v = (i * q + p) % n + 1;
        if (u > v) swap(u, v);
        modify(1, u, v, i);
    }

    for (int i = 1; i <= n; ++i) {
   
        int ans = query(1, i);
        cout << ans << "\n";
    }

    return 0;
}

*警示后人

如果线段树不是带有延迟标记的, 那么如果进行修改只能修改到点上, 如果是带有延迟标记的可以进行区间修改