「PA 2020」Mieszanie kolorów 题解

算法思路

本题使用差分数组技术来高效处理区间更新操作，然后通过颜色混合规则统计绿色油漆的数量。

关键观察

1. 颜色混合规则

根据题目描述，绿色油漆的条件是：

• 包含黄色和蓝色
• 但不包含红色

即数学表达式：$黄色 > 0 \land 蓝色 > 0 \land 红色 = 0$

2. 差分数组原理

对于每个颜色类型，使用差分数组来记录区间添加操作：

• 在 $l$ 位置 $+1$，在 $r+1$ 位置 $-1$
• 通过前缀和还原每个位置的实际计数

代码解析

差分数组初始化

int n, m, l, r, k, ans, red[1000010], yel[1000010], bul[1000010];

三个数组分别记录红色、黄色、蓝色的差分信息。

处理操作

while (m--) {
    cin >> l >> r >> k;
    
    if (k == 1) {          // 黄色
        yel[l]++;
        yel[r + 1]--;
    } else if (k == 2) {   // 蓝色  
        bul[l]++;
        bul[r + 1]--;
    } else {               // 红色
        red[l]++;
        red[r + 1]--;
    }
}

前缀和还原与统计

for (int i = 1; i <= n; i++) {
    // 计算每个位置的实际颜料计数
    red[i] += red[i - 1];
    yel[i] += yel[i - 1]; 
    bul[i] += bul[i - 1];
    
    // 检查绿色条件：有黄色和蓝色，但没有红色
    if (!red[i] and yel[i] and bul[i]) {
        ans++;
    }
}

算法正确性

差分数组的正确性

• 每次操作在 $l$ 处 $+1$ 表示从该位置开始有这个颜色
• 在 $r+1$ 处 $-1$ 表示到这个位置结束
• 前缀和计算后，$color[i]$ 表示第 $i$ 个罐子被添加该颜色的次数

绿色判断条件

根据颜色混合表：

• 绿色 = 黄色 + 蓝色
• 需要确保没有红色干扰（否则会变成棕色）

因此条件为：$红色=0 \land 黄色>0 \land 蓝色>0$

复杂度分析

• 时间复杂度：$O(n + m)$
  • 处理 $m$ 次操作：$O(m)$
  • 前缀和计算和统计：$O(n)$
• 空间复杂度：$O(n)$