[PA 2020] Mieszanie kolorów

Luogu

IDLGP9094

Time2500ms

Memory256MB

DifficultyP2

2020前缀和差分PA（波兰）

**题目译自 [PA 2020](https://sio2.mimuw.edu.pl/c/pa-2020-1/dashboard/) Runda 1 [Mieszanie kolorów](https://sio2.mimuw.edu.pl/c/pa-2020-1/p/kol/)** Byteasar 正准备给栅栏涂漆。他已经准备了 $n$ 罐白色油漆，他把这些油漆排列成一排，从 $1$ 到 $n$ 编号。他想用这些油漆，但他不想把栅栏涂成白色。他委托了调色专家，调色专家有三种颜料：黄色、蓝色和红色。专家进行了 $m$ 次操作，其中第 $i$ 次操作是向编号在 $l_i$ 到 $r_i$ 之间（包括两端）的所有罐子中加入某种颜料。油漆的最终颜色取决于被添加到其中的颜料。添加的颜料按照下表和图示进行混合。 | 颜料 | 颜色 | | :----------------: | :--: | | 无 | 白色 | | 黄色 | 黄色 | | 蓝色 | 蓝色 | | 红色 | 红色 | | 黄色 + 蓝色 | 绿色 | | 黄色 + 红色 | 橙色 | | 蓝色 + 红色 | 紫色 | | 黄色 + 蓝色 + 红色 | 棕色 | ![](https://cdn.luogu.com.cn/upload/image_hosting/zow92g6w.png) Byteasar 想要给栅栏涂成一种颜色。思来想去，他选择了绿色，因为绿色代表了你常会在算法竞赛中看到的 Accepted。他想知道现在有多少罐油漆是绿色的，请帮他数数。 ## Input 第一行两个整数 $n,m$，分别表示油漆的罐数和专家进行的操作数。接下来 $m$ 行，每行三个整数 $l_i,r_i,k_i$，表示在第 $i$ 次操作中向编号在 $l_i$ 到 $r_i$ 之间（包括两端）的罐子中加入颜料。加入的颜料是黄色（$k_i=1$），蓝色（$k_i=2$）或红色（$k_i=3$）中的一种。 ## Output 输出一行一个整数，表示在所有操作之后绿色油漆的罐数。 [samples] ## Note #### 样例 1 解释操作结束后，这些油漆分别是蓝色、绿色、黄色、绿色、绿色、棕色、橙色、黄色和白色的。因此，只有三罐油漆是绿色。 ------------ #### 数据范围 **本题采用捆绑测试** 对于 $100\%$ 的数据，保证 $1\le n,m\le 10^6$，$1\le l_i\le r_i\le n$，$1\le k_i\le 3$。

Samples

Input #1

Output #1

API Response (JSON)

{
  "problem": {
    "name": "[PA 2020] Mieszanie kolorów",
    "description": {
      "content": "**题目译自 [PA 2020](https://sio2.mimuw.edu.pl/c/pa-2020-1/dashboard/) Runda 1 [Mieszanie kolorów](https://sio2.mimuw.edu.pl/c/pa-2020-1/p/kol/)** Byteasar 正准备给栅栏涂漆。他已经准备了 $n$ 罐白色油漆，他把这些油漆排列成一排，从 $1$ 到 $",
      "description_type": "Markdown"
    },
    "platform": "Luogu",
    "limit": {
      "time_limit": 2500,
      "memory_limit": 262144
    },
    "difficulty": {
      "LuoguStyle": "P2"
    },
    "is_remote": true,
    "is_sync": true,
    "sync_url": null,
    "sign": "LGP9094"
  },
  "statements": [
    {
      "statement_type": "Markdown",
      "content": "**题目译自 [PA 2020](https://sio2.mimuw.edu.pl/c/pa-2020-1/dashboard/) Runda 1 [Mieszanie kolorów](https://sio2.mimuw.edu.pl/c/pa-2020-1/p/kol/)**\n\nByteasar 正准备给栅栏涂漆。他已经准备了 $n$ 罐白色油漆，他把这些油漆排列成一排，从 $1$ 到 $...",
      "is_translate": false,
      "language": "English"
    }
  ]
}

Full JSON Raw Segments