题解 | 染色

#include <iostream>
#include <vector>
using namespace std;

// 思维流：我们不必真的如题目所想将三种颜色进行融合，我们只需要知道对于一个绿色油漆桶就是要出现黄色蓝色且不要出现红色。那么思路便明了了：
// 建立三种颜色的差分数组，得到每个油罐桶的被三种颜料分别灌入的总次数（三种颜色的前缀和数组）
// 如果对于某个油漆桶，就看它的黄色和蓝色前缀和数组是否大于1，红色是否为0，即可判断能否变绿

int main() {
    int n, m;
    cin >> n >> m; // 油漆罐的数量和加色操作的次数
    vector<int> d_yell(n+2,0); // 油漆桶编号为1~n
    vector<int> d_blue(n+2,0);
    vector<int> d_red(n+2,0);
    while (m--) {
        int l, r, k; // k为本次加入颜料的类别
        cin >> l >> r >> k;
        if (k == 1) {
            d_yell[l] += 1;
            d_yell[r+1] -= 1;
        }
        else if (k == 2) {
            d_blue[l] += 1;
            d_blue[r+1] -= 1;
        }
        else if (k == 3) {
            d_red[l] += 1;
            d_red[r+1] -= 1;
        }
    }
    vector<int>summ_yell(n+1,0);
    vector<int>summ_blue(n+1,0);
    vector<int>summ_red(n+1,0);
    int cnt_green = 0;
    for (int i = 1; i <= n; i++) {
        summ_yell[i] = summ_yell[i-1] + d_yell[i];
        summ_blue[i] = summ_blue[i-1] + d_blue[i];
        summ_red[i] = summ_red[i-1] + d_red[i];
        if (summ_yell[i] >= 1 && summ_blue[i] >= 1 && summ_red[i] == 0) {
            cnt_green++;
        }
    }
    cout << cnt_green;
}