F. [PA 2020] Mieszanie kolorów

A B C D E F G H I J K L M N O P Q R S T U V W X Y Z

Type: RemoteJudge

2500ms

256MiB

You cannot submit for this problem because the contest is ended. You can click "Open in Problem Set" to view this problem in normal mode.

题目描述

题目译自 PA 2020 Runda 1 Mieszanie kolorów

Byteasar 正准备给栅栏涂漆。他已经准备了 $n$ 罐白色油漆，他把这些油漆排列成一排，从 $1$ 到 $n$ 编号。他想用这些油漆，但他不想把栅栏涂成白色。他委托了调色专家，调色专家有三种颜料：黄色、蓝色和红色。专家进行了 $m$ 次操作，其中第 $i$ 次操作是向编号在 $l_i$ 到 $r_i$ 之间（包括两端）的所有罐子中加入某种颜料。

油漆的最终颜色取决于被添加到其中的颜料。添加的颜料按照下表和图示进行混合。

颜料	颜色
无	白色
黄色
蓝色
红色
黄色 + 蓝色	绿色
黄色 + 红色	橙色
蓝色 + 红色	紫色
黄色 + 蓝色 + 红色	棕色

Byteasar 想要给栅栏涂成一种颜色。思来想去，他选择了绿色，因为绿色代表了你常会在算法竞赛中看到的 Accepted。他想知道现在有多少罐油漆是绿色的，请帮他数数。

输入格式

第一行两个整数 $n,m$ ，分别表示油漆的罐数和专家进行的操作数。

接下来 $m$ 行，每行三个整数 $l_i,r_i,k_i$ ，表示在第 $i$ 次操作中向编号在 $l_i$ 到 $r_i$ 之间（包括两端）的罐子中加入颜料。加入的颜料是黄色（ $k_i=1$ ），蓝色（ $k_i=2$ ）或红色（ $k_i=3$ ）中的一种。

输出格式

输出一行一个整数，表示在所有操作之后绿色油漆的罐数。

提示

样例 1 解释

操作结束后，这些油漆分别是蓝色、绿色、黄色、绿色、绿色、棕色、橙色、黄色和白色的。因此，只有三罐油漆是绿色。

数据范围

本题采用捆绑测试

对于 $100\%$ 的数据，保证 $1\le n,m\le 10^6$ ， $1\le l_i\le r_i\le n$ ， $1\le k_i\le 3$ 。

2025年CSP-J前缀和差分

Not Claimed

Status: Done
Problem: 26
Open Since: 2025-8-7 0:00
Deadline: 2025-9-30 23:59
Extension: 24 hour(s)