[PA 2020] Mieszanie kolorów

GitHub跳转原题关系图返回列表

分别用三个差分数组记录黄色、蓝色、红色的区间添加次数，最后统计有黄有蓝且无红的位置。

OJ: luogu

题目 ID: P9094

难度:普及-

标签:差分前缀和模拟

日期: 2025-12-24 10:34

目录

  1. 题意
  2. 思路
    1. 为什么只关心是否大于 0
  3. 代码
  4. 复杂度
  5. 总结

题意

有 n 罐初始为白色的油漆，接下来有 m 次操作。
每次操作给区间 [l,r] 内所有油漆加入一种颜料：

  • 1：黄色
  • 2：蓝色
  • 3：红色

一罐油漆最终是绿色，当且仅当它加入过黄色和蓝色，并且没有加入过红色。
要求统计最终有多少罐油漆是绿色。

思路

先看一个最直接的朴素模拟：

cpp
#include <bits/stdc++.h>
using namespace std;

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int n, m;
    cin >> n >> m;

    vector<array<int, 4>> paint(n + 1);

    for (int i = 1; i <= m; ++i) {
        int l, r, k;
        cin >> l >> r >> k;

        // 小数据可信解：直接给区间内每一罐油漆打上颜色标记。
        for (int pos = l; pos <= r; ++pos) {
            paint[pos][k] = 1;
        }
    }

    int ans = 0;
    for (int i = 1; i <= n; ++i) {
        if (paint[i][1] && paint[i][2] && !paint[i][3]) {
            ++ans;
        }
    }

    cout << ans << '\n';
    return 0;
}

朴素做法对每次操作都枚举区间 [l,r] 内所有位置，给这些位置打颜色标记。
但 n,m 都可以到 10^6，最坏会达到 10^12 级别，不能直接模拟。

注意到每种颜色的操作都是“给一个区间添加一次标记”。
因此可以为三种颜色分别开一个差分数组：

  • 黄色差分数组记录哪些位置被加过黄色；
  • 蓝色差分数组记录哪些位置被加过蓝色；
  • 红色差分数组记录哪些位置被加过红色。

对于一次操作 (l,r,k)，只需要：

text
diff[k][l] += 1
diff[k][r+1] -= 1

读完所有操作后，从左到右对三个差分数组分别做前缀和。
对每个位置 i，只要满足：

text
yellow[i] > 0
blue[i] > 0
red[i] == 0

这个位置就是绿色。

为什么只关心是否大于 0

这张表说明最终颜色和三种颜料是否出现之间的关系。

黄色 蓝色 红色 最终是否绿色
有 有 无 是
有 有 有 否，变成棕色
有 无 无 否，黄色
无 有 无 否，蓝色

同一种颜料被加入多次，仍然只表示“有这种颜料”。
所以还原差分后，不需要知道具体加了几次，只需要判断次数是否大于 0。

代码

cpp
#include <bits/stdc++.h>
using namespace std;

const int MAXN = 1000000 + 5;

int n, m;
int diff_color[4][MAXN];

void add_color(int color, int left_pos, int right_pos) {
    diff_color[color][left_pos] += 1;
    diff_color[color][right_pos + 1] -= 1;
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    cin >> n >> m;

    for (int i = 1; i <= m; ++i) {
        int l, r, k;
        cin >> l >> r >> k;
        add_color(k, l, r);
    }

    int ans = 0;
    for (int i = 1; i <= n; ++i) {
        diff_color[1][i] += diff_color[1][i - 1];
        diff_color[2][i] += diff_color[2][i - 1];
        diff_color[3][i] += diff_color[3][i - 1];

        // 绿色 = 有黄色 + 有蓝色 + 没有红色。
        if (diff_color[1][i] > 0 && diff_color[2][i] > 0 && diff_color[3][i] == 0) {
            ++ans;
        }
    }

    cout << ans << '\n';
    return 0;
}

复杂度

  • 处理 m 次操作，每次 O(1)O(1)。
  • 最后扫描 n 个位置。
  • 总时间复杂度 O(n+m)O(n+m)。
  • 使用三个长度为 n 的差分数组，空间复杂度 O(n)O(n)。

总结

这题是“一维区间修改，最后统一统计”的典型差分题。
关键是不要把颜色混合过程想复杂：绿色只需要满足“有黄、有蓝、无红”，所以三种颜色分别维护即可。