[PA 2020] 混合颜料(Mixing Colors) 题解

思路分析

分别对黄（$1$）、蓝（$2$）、红（$3$）三种颜料各开一个一维差分数组 diff[k][1..n+1]。每次操作 $[l, r, k]$ 令 diff[k][l]++, diff[k][r + 1]--。最后求前缀和还原每个罐子被加入三种颜料的次数，统计同时满足「黄 $> 0$、蓝 $> 0$、红 $= 0$」的罐子数量即可。时间复杂度 $O(n + m)$。

参考代码

#include <iostream>
using namespace std;

const int MX = 1000005;
int d1[MX], d2[MX], d3[MX];

int main()
{
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int n, m;
    if (!(cin >> n >> m)) return 0;
    for (int i = 0; i < m; ++i)
    {
        int l, r, k;
        cin >> l >> r >> k;
        if (k == 1) { d1[l]++; d1[r + 1]--; }
        else if (k == 2) { d2[l]++; d2[r + 1]--; }
        else { d3[l]++; d3[r + 1]--; }
    }
    int c1 = 0, c2 = 0, c3 = 0, ans = 0;
    for (int i = 1; i <= n; ++i)
    {
        c1 += d1[i];
        c2 += d2[i];
        c3 += d3[i];
        if (c1 > 0 && c2 > 0 && c3 == 0) ++ans;
    }
    cout << ans << "\n";
    return 0;
}