P16698 [CSPro 29] 施肥

洛谷的测试数据仅供民间交流使用，非官方测试数据。官方评测链接：。

春天到了，西西艾弗岛上的 $n$ 块田地需要施肥了。$n$ 块田地编号为 $1, 2, \cdots, n$，按照编号从小到大的顺序排成一列。 为了给田地施肥，顿顿准备了 $m$ 辆施肥车。但是由于土地的松软程度不同，施肥车的质量不一，不一定每一辆施肥车都能给每一块田地施肥。其中，第 $i$ 辆施肥车**只能恰好**从第 $l_i$ 块田地开到第 $r_i$ 块田地，并给编号在 $l_i$ 与 $r_i$ 之间的田地（包含 $l_i$ 和 $r_i$）都施一遍肥。其中 $1 \le l_i < r_i \le n$。 顿顿希望制定一个施肥的计划。首先，他将选定二元组 $(L, R)$ ($1 \le L < R \le n$)，并选择只给编号在 $L, R$ 之间（包含 $L, R$）的田地施肥。接着，他会从使用这 $m$ 辆施肥车中的一部分（或全部）对田地施肥。他想要保证：**编号在 $L$ 和 $R$ 之内的田地至少被某一辆施肥车施了一次肥，且编号范围外的田地都没有被施过肥。** 现在，他想知道，他能够选择多少种不同的二元组 $(L, R)$ 作为施肥范围，使得可以选出一部分（或全部）施肥车，完成他的目标。

从标准输入读入数据。 第一行输入两个正整数 $n, m$，表示田地的块数和施肥车的辆数。数据保证 $2 \le n \le 2 \cdot 10^5$, $1 \le m \le 2 \cdot 10^5$。 接下来 $m$ 行，第 $i$ 行输入两个正整数 $l_i, r_i$，表示第 $i$ 辆施肥车的施肥范围从第 $l_i$ 块田地到第 $r_i$ 块田地。数据保证 $1 \le l_i < r_i \le n$。

输出到标准输出。 输出一个正整数，表示顿顿能够选择多少种不同的二元组 $(L, R)$ 作为施肥范围，使得他可以选出一部分（或全部）施肥车，完成他的目标。

### 样例 1 解释 在这组样例中，顿顿可以选择 $6$ 种不同的二元组 $(L, R)$。 第一种：选择 $(L, R) = (1, 2)$，并只选取第 $1$ 个施肥车施肥。 第二种：选择 $(L, R) = (3, 4)$，并只选取第 $2$ 个施肥车施肥。 第三种：选择 $(L, R) = (2, 3)$，并只选取第 $3$ 个施肥车施肥。 第四种：选择 $(L, R) = (1, 4)$，并选取第 $1$ 个和第 $2$ 个施肥车施肥。 第五种：选择 $(L, R) = (1, 3)$，并选取第 $1$ 个和第 $3$ 个施肥车施肥。 第六种：选择 $(L, R) = (2, 4)$，并选取第 $2$ 个和第 $3$ 个施肥车施肥。 ### 样例 2 见题目目录下的 `2.in` 与 `2.ans`。 这个样例满足 $n, m \le 18$。 ### 样例 3 见题目目录下的 `3.in` 与 `3.ans`。 这个样例满足 $n, m \le 50$。 ### 样例 4 见题目目录下的 `4.in` 与 `4.ans`。 这个样例满足 $n, m \le 400$。 ### 样例 5 见题目目录下的 `5.in` 与 `5.ans`。 这个样例满足 $n, m \le 3000$。 ### 样例 6 见题目目录下的 `6.in` 与 `6.ans`。 这个样例满足特殊性质 A。 ### 样例 7 见题目目录下的 `7.in` 与 `7.ans`。 这个样例满足 $n, m \le 200000$。 ### 子任务 | 测试点编号 | $n \le$ | $m \le$ | 特殊性质 | |:----------:|:---------:|:---------:|:--------:| | $1$ | $18$ | $18$ | 无 | | $2$ | ^ | ^ | ^ | | $3$ | ^ | ^ | ^ | | $4$ | $50$ | $50$ | ^ | | $5$ | ^ | ^ | ^ | | $6$ | $400$ | $400$ | ^ | | $7$ | ^ | ^ | ^ | | $8$ | $3000$ | $3000$ | ^ | | $9$ | ^ | ^ | ^ | | $10$ | ^ | ^ | ^ | | $11$ | ^ | ^ | ^ | | $12$ | ^ | ^ | ^ | | $13$ | $200000$ | $200000$ | A | | $14$ | ^ | ^ | ^ | | $15$ | ^ | ^ | ^ | | $16$ | ^ | ^ | 无 | | $17$ | ^ | ^ | ^ | | $18$ | ^ | ^ | ^ | | $19$ | ^ | ^ | ^ | | $20$ | ^ | ^ | ^ | 特殊性质 A：保证任意两个施肥车的施肥范围不存在相互包含的关系，也就是说，对任意 $1 \le i < j \le m$，$l_i < l_j, r_i < r_j$ 或 $l_i > l_j, r_i > r_j$。