染色

思路

题目说的是：有 个油漆桶，初始都是白色。进行 次操作，每次往区间 的油漆桶里加一种颜料（1=黄色，2=蓝色，3=红色）。颜料混合规则：黄+蓝=绿，黄+红=橙，蓝+红=紫，三色全加=棕。问最终有多少桶是绿色的。

绿色的条件是什么？有黄、有蓝、没有红。

这是一个典型的差分数组问题。区间加操作用差分数组来做是最自然的。

关键在于：三种颜料是独立的，每种颜料只需要知道"有没有被加过"。所以我们对三种颜料分别维护一个差分数组。

具体做法：

  1. 开三个差分数组 ，分别对应黄、蓝、红三种颜料。
  2. 对于每次操作 ，在对应的差分数组上做 ++，--。
  3. 最后扫一遍，对三个差分数组分别求前缀和，得到每个位置上各颜料的添加次数 。
  4. 如果 且 且 ，说明这个桶是绿色的，答案加 1。

用样例验证一下：9 个桶，5 次操作后：

  • 桶 1：蓝 → 蓝色
  • 桶 2：黄+蓝 → 绿色 ✓
  • 桶 3：黄 → 黄色
  • 桶 4：黄+蓝 → 绿色 ✓
  • 桶 5：黄+蓝+蓝 → 绿色 ✓（蓝加了两次，但只要有就行）
  • 桶 6：蓝+红+蓝 → 紫色（有蓝有红没黄）
  • 桶 7：黄+红 → 橙色
  • 桶 8：黄 → 黄色
  • 桶 9：白色

绿色有 3 个，正确！

代码

#include <bits/stdc++.h>
using namespace std;
int main(){
    int n, m;
    scanf("%d%d", &n, &m);
    vector<int> d1(n+2,0), d2(n+2,0), d3(n+2,0);
    for(int i=0;i<m;i++){
        int l,r,c;
        scanf("%d%d%d",&l,&r,&c);
        if(c==1){ d1[l]++; d1[r+1]--; }
        else if(c==2){ d2[l]++; d2[r+1]--; }
        else{ d3[l]++; d3[r+1]--; }
    }
    int ans=0, s1=0, s2=0, s3=0;
    for(int i=1;i<=n;i++){
        s1+=d1[i]; s2+=d2[i]; s3+=d3[i];
        if(s1>0 && s2>0 && s3==0) ans++;
    }
    printf("%d\n",ans);
    return 0;
}

import java.util.Scanner;
public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt(), m = sc.nextInt();
        int[] d1 = new int[n+2], d2 = new int[n+2], d3 = new int[n+2];
        for (int i = 0; i < m; i++) {
            int l = sc.nextInt(), r = sc.nextInt(), c = sc.nextInt();
            if (c == 1) { d1[l]++; d1[r+1]--; }
            else if (c == 2) { d2[l]++; d2[r+1]--; }
            else { d3[l]++; d3[r+1]--; }
        }
        int ans = 0, s1 = 0, s2 = 0, s3 = 0;
        for (int i = 1; i <= n; i++) {
            s1 += d1[i]; s2 += d2[i]; s3 += d3[i];
            if (s1 > 0 && s2 > 0 && s3 == 0) ans++;
        }
        System.out.println(ans);
    }
}

import sys
input = sys.stdin.readline

def main():
    n, m = map(int, input().split())
    d1 = [0] * (n + 2)
    d2 = [0] * (n + 2)
    d3 = [0] * (n + 2)
    for _ in range(m):
        l, r, c = map(int, input().split())
        if c == 1:
            d1[l] += 1; d1[r+1] -= 1
        elif c == 2:
            d2[l] += 1; d2[r+1] -= 1
        else:
            d3[l] += 1; d3[r+1] -= 1
    ans = 0
    s1 = s2 = s3 = 0
    for i in range(1, n + 1):
        s1 += d1[i]; s2 += d2[i]; s3 += d3[i]
        if s1 > 0 and s2 > 0 and s3 == 0:
            ans += 1
    print(ans)

main()

const readline = require('readline');
const rl = readline.createInterface({ input: process.stdin });
const lines = [];
rl.on('line', line => lines.push(line));
rl.on('close', () => {
    let idx = 0;
    const [n, m] = lines[idx++].split(' ').map(Number);
    const d1 = new Array(n + 2).fill(0);
    const d2 = new Array(n + 2).fill(0);
    const d3 = new Array(n + 2).fill(0);
    for (let i = 0; i < m; i++) {
        const [l, r, c] = lines[idx++].split(' ').map(Number);
        if (c === 1) { d1[l]++; d1[r+1]--; }
        else if (c === 2) { d2[l]++; d2[r+1]--; }
        else { d3[l]++; d3[r+1]--; }
    }
    let ans = 0, s1 = 0, s2 = 0, s3 = 0;
    for (let i = 1; i <= n; i++) {
        s1 += d1[i]; s2 += d2[i]; s3 += d3[i];
        if (s1 > 0 && s2 > 0 && s3 === 0) ans++;
    }
    console.log(ans);
});

复杂度

  • 时间复杂度：，差分数组建立 ，扫描还原 。
  • 空间复杂度：，三个差分数组各 。