B4047 [语言月赛 202410] 校门外的施工

题目描述

某校大门外有 $m$ 棵树，从左到右编号依次为 $1,2,\ldots, m$。同时，第 $i$ 棵树和第 $i+1$ 棵树中间有一片草坪。树和草坪统称绿化。

接下来按时间顺序发生了 $n$ 次施工，分为两种：

• $\texttt{1}\ l\ r$，一次施工破坏了第 $l$ 棵树和第 $r$ 棵树之间（不含这两棵树）的所有绿化。

• $\texttt{2}\ l\ r$，一次施工破坏了第 $l$ 棵树和第 $r$ 棵树之间（包含这两棵树）的所有绿化。

请计算 $n$ 次施工结束后，还剩下几棵树、几片草坪没有被破坏。

输入格式

输入的第一行有两个正整数 $m,n$，分别表示树的数量和施工的次数。

之后有 $n$ 行，每行格式形如 $\texttt{1}\ l\ r$ 或 $\texttt{2}\ l\ r$，表示一次施工。

输出格式

输出一行两个整数，表示答案。其中第一个整数表示剩下几棵树，第二个整数表示剩下几片草坪。

输入输出样例 #1

输入 #1

6 2

2 2 3

2 4 6

输出 #1

1 2

输入输出样例 #2

输入 #2

6 3

1 1 3

2 2 4

2 4 5

输出 #2

2 1

输入输出样例 #3

输入 #3

6 3

1 1 2

2 3 4

1 2 3

输出 #3

4 2

说明/提示

【样例 1 解释】

下面用一张表格来表示所有绿化的存活情况，其中 + 表示存活，- 表示被破坏。

|树的编号|1|草坪|2|草坪|3|草坪|4|草坪|5|草坪|6|

|:-:|:-:|:-:|:-:|:-:|:-:|:-:|:-:|:-:|:-:|:-:|:-:|

|第一次施工后|+|+|-|-|-|+|+|+|+|+|+|

|第二次施工后|+|+|-|-|-|+|-|-|-|-|-|

我们发现 编号为 $1$ 的树被剩下，并且 $1,2$ 之间的草坪、$3,4$ 之间的草坪被剩下。

【样例 2 解释】

使用类似的办法记录所有绿化的情况。

|树的编号|1|草坪|2|草坪|3|草坪|4|草坪|5|草坪|6|

|:-:|:-:|:-:|:-:|:-:|:-:|:-:|:-:|:-:|:-:|:-:|:-:|

|第一次施工后|+|-|-|-|+|+|+|+|+|+|+|

|第二次施工后|+|-|-|-|-|-|-|+|+|+|+|

|第三次施工后|+|-|-|-|-|-|-|-|-|+|+|

剩下第 $1,6$ 棵树和第 $5,6$ 棵树中间的草坪。

【数据范围】

本题共有 $10$ 个测试点，每个 $10$ 分。

测试点 $1,2$ 保证 $n=1$。

测试点 $3\sim 5$ 保证剩余草坪数为 $0$。

测试点 $6,7$ 保证只有第一种类型的施工。

对于所有测试点，保证 $1\le m,n\le 5000$，并且对于每次操作，保证 $1\le l<r\le m$。