题解 | 染色

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

using ll=long long;
using ull=unsigned long long;
using i128=__int128_t;
using u128=__uint128_t;
using ld=long double;

void solve()
{//这道题我们可以很自然的想到使用差分 但是问题在于 假如只有一个差分数组 我们无法根据数值大小来判断一个桶拥有哪种油漆
//所以我们可以想到 维护三个差分数组 分别判断三种颜色是否加入 差分过程也很简单 例如k==1时 我们对第一个数组进行差分
//最后对差分数组进行判断 对于第i个元素 数组1和数组2大于0 数组3=0 即为绿色 计数
    int n,q,l,r,k,cnt=0;
    cin >> n >> q;
    vector<int>v1(n+2,0),v2(n+2,0),v3(n+2,0);//防止越界
    while(q--)
    {
        cin >> l >> r >> k;
        if(k==1)
        {
            v1[l]+=1;
            v1[r+1]-=1;
        }
        else if(k==2)
        {
            v2[l]+=1;
            v2[r+1]-=1;
        }
        else
        {
            v3[l]+=1;
            v3[r+1]-=1;
        }
    }
    for(int i=1;i<=n;i++)
    {
        v1[i]+=v1[i-1];
        v2[i]+=v2[i-1];
        v3[i]+=v3[i-1];
        if(v1[i]>0&&v2[i]>0&&v3[i]==0) cnt++;//有黄有蓝无红 计数
    }
    cout << cnt;
}

int main()
{
	ios::sync_with_stdio(false);
	cin.tie(nullptr);
	
	int t=1;
	//cin >> t;
	
	while(t--)
	{
		solve();
	}
	return 0;
}