题解 | 染色

#include<bits/stdc++.h>
using namespace std;
#define int long long
const int N = 1e6+100;
int a[5][N];
void solve()
{
    int n,k;cin>>n>>k;
    int l,r,col;
    int ans = 0;
    for(int i = 1 ; i <= k ; ++i)
    {
        cin>>l>>r>>col;
        a[col][l]++,a[col][r+1]--;
    }
    for(int i = 1 ; i <= n ; ++i)
    {
        for(int j = 1 ; j <= 3 ; ++j)
            a[j][i] += a[j][i-1];
        if(a[1][i] && a[2][i] && a[3][i] == 0)ans++;
    }
    cout<<ans<<endl;
}
signed main()
{
    int t = 1;
//     cin>>t;
    while(t--)
        solve();
    return 0;
}

其实就是一个差分。

因为对区间的操作可以转化成单点操作更优。

对于数组a[col][i]，表示第i个元素有没有col颜色。等于0表示没有，否则就是有。

在统计的时候只需要判断：是不是有黄有绿但是没有红色就好了。

一开始不是很想写多组的差分，想到了一个方法：黄色用1，绿色用2，红色用4。

这样子绿色就等于3，橙色就等于5，紫色就等于6，棕色就等于7，恰好可以错开的表示。

但是考虑到一个区间可能被一种颜色染两次，这种情况就会出错。。。