← 返回题目列表

AtCoder · icpc2015autumn_h

H. 甜甜圈装饰

中文机器翻译题面 查看原题

问题陈述

甜甜圈制造商的早晨很早。 D 先生,也被称为甜甜圈先生,是一位出色的甜甜圈制造商。 同样在今天,他去厨房准备在日出之前制作甜甜圈。

转眼之间,D先生熟练的手就煎好了$N$甜甜圈。 但这些甜甜圈不得在陈列柜中展示。 填充奶油,蘸上巧克力,浇上一些可爱的、色彩缤纷的东西等等,需要进行一些装饰任务。 有编号为 $1$ 到 $K$ 的 $K$ 任务,每个任务必须按照 $1、2、\ldots、K$ 的顺序恰好完成一次,才能将甜甜圈作为特价商品完成。

D先生立即将$N$甜甜圈排成一排。 他似乎打算一次依次完成每项装饰任务。 然而,他到底在做什么?昨天晚上熬夜的D先生,在每次任务的连续间隔内只装饰了一部分甜甜圈。 这显然是一个错误! 不仅如此,有些任务他会做零次或者几次,而且任务的顺序也是混乱的。 没有经过正确工艺装饰的甜甜圈不能作为商品出售,所以他应该把它们扔掉。

幸运的是,有数据记录了他所做的一系列任务。 数据包含以下信息:对于每个任务,装饰甜甜圈的连续间隔 $[l, r]$ 以及任务的 ID $x$。 请编写一个程序,根据给定的记录数据,枚举可以在陈列柜中作为促销商品显示的甜甜圈的数量。


输入

输入由单个测试用例组成。测试用例的格式如下。

$N$ $K$
$T$
$l_1$ $r_1$ $x_1$
:
:
$l_T$ $r_T$ $x_T$

第一行包含两个整数$N$和$K$,其中$N$ ($1 \leq N \leq 200{,}000$)是D先生炸的甜甜圈的数量,$K$ ($1 \leq K \leq 200{,}000$)是应该对甜甜圈应用装饰任务的数量。 第二行包含一个整数$T$($1 \leq T \leq 200{,}000$),表示D先生所做任务的信息数量。 接下来的 $T$ 行包含三个整数 $l_i$、$r_i$ 和 $x_i$,代表 D 先生执行的第 $i$ 个任务:第 $i$ 个任务应用于甜甜圈的区间 $[l_i, r_i]$ ($1 \leq l_i \leq r_i \leq N$),并且 ID 为 $x_i$ ($1 \leq x_i \leq K$)。

输出

输出可作为促销商品提供的甜甜圈的数量。



样本输入 1

3 2
3
1 2 1
2 3 2
3 3 1

样本输入 1 的输出

1

示例输入 2

5 3
6
2 3 1
1 3 2
4 5 1
2 4 3
3 5 2
5 5 3

样本输入 2 的输出

2

示例输入 3

10 1
2
2 9 1
5 7 1

样本输入 3 的输出

5