自动搬运

查看原文

来自洛谷，原作者为

	WaterSky 泠泠风自扬·澹澹夜未央

搬运于2025-08-24 22:45:18，当前版本为作者最后更新于2023-03-26 18:43:36，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

题目传送门。

开始讲解：

思路：

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

既然知道了用差分，那么就需要深入的研究怎么使用这一个算法。首先，题目中说：有三种颜色：红、黄、蓝。在 $M$ 个 操作中，让从 $x$ 到 $y$ 的这一个区间加上这三种颜色的一种。所以，可以开三个数组，分别储存这三种颜色的添加情况，最后再判断处理。

我的代码（码丑勿喷）：

#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;
}