P9094题解

· · 题解

P9094 [PA 2020] Mieszanie kolorów

差分。因为它求得是一个数列经过某一些操作后，求出某个区间的数量，而差分这一个算法，就是为了解决这一个类型的题目，故而用差分。

首先，题目中说：有三种颜色：红、黄、蓝。在 M 个 操作中，让从 x 到 y 的这一个区间加上这三种颜色的一种。所以，可以开三个数组，分别储存这三种颜色的添加情况，最后再判断处理。 :::info[Code.]

#include<bits/stdc++.h>
using namespace std;
long long n,m,A[1000005],B[1000005],C[1000005],x,y,z,ans;//定义
int main()
{
    cin>>n>>m;//输入
    for(int i=1;i<=m;i++)
    {
        cin>>x>>y>>z;//输入
        if(z==1) A[x]++,A[y+1]--;//黄色颜料处理
        if(z==2) B[x]++,B[y+1]--;//蓝色颜料处理
        if(z==3) C[x]++,C[y+1]--;//红色颜料处理
    }
    for(int i=1;i<=n;i++) A[i]+=A[i-1],B[i]+=B[i-1],C[i]+=C[i-1];//前缀差分
    for(int i=1;i<=n;i++) 
    if( A[i] && B[i] && !C[i]) ans++; //判断是否为绿色
    cout<<ans;//输出答案
    return 0;//最好return 0;
}

:::