P16698 [CSPro 29] Fertilization.

Luogu’s testdata is for community exchange only and is not official testdata. Official judging link: .

Spring has come, and the $n$ fields on Xixi-Aifu Island need to be fertilized. The $n$ fields are numbered $1, 2, \cdots, n$, arranged in a line in increasing order of their indices. To fertilize the fields, Dundun prepared $m$ fertilizing trucks. However, due to different soil softness and different truck weights, not every truck can fertilize every field. Specifically, the $i$-th truck **can only exactly** drive from field $l_i$ to field $r_i$, and fertilize all fields whose indices are between $l_i$ and $r_i$ (including $l_i$ and $r_i$). Here, $1 \le l_i < r_i \le n$. Dundun wants to make a fertilization plan. First, he will choose an ordered pair $(L, R)$ ($1 \le L < R \le n$), and decide to fertilize only the fields with indices between $L$ and $R$ (including $L$ and $R$). Then, he will choose some (or all) of the $m$ trucks to fertilize the fields. He wants to ensure that: **every field with index in $[L, R]$ is fertilized at least once by some truck, and no field outside this range is fertilized.** Now he wants to know how many different ordered pairs $(L, R)$ he can choose as the fertilization range such that he can select some (or all) trucks to achieve his goal.

Read input from standard input. The first line contains two positive integers $n, m$, representing the number of fields and the number of trucks. It is guaranteed that $2 \le n \le 2 \cdot 10^5$, $1 \le m \le 2 \cdot 10^5$. The next $m$ lines describe the trucks. The $i$-th line contains two positive integers $l_i, r_i$, representing that the $i$-th truck fertilizes from field $l_i$ to field $r_i$. It is guaranteed that $1 \le l_i < r_i \le n$.

Output to standard output. Output one positive integer, the number of different ordered pairs $(L, R)$ that Dundun can choose as the fertilization range such that he can select some (or all) trucks to achieve his goal.

### Explanation for Sample 1 In this sample, Dundun can choose $6$ different ordered pairs $(L, R)$. The first: choose $(L, R) = (1, 2)$, and select only the $1$-st truck. The second: choose $(L, R) = (3, 4)$, and select only the $2$-nd truck. The third: choose $(L, R) = (2, 3)$, and select only the $3$-rd truck. The fourth: choose $(L, R) = (1, 4)$, and select the $1$-st and the $2$-nd trucks. The fifth: choose $(L, R) = (1, 3)$, and select the $1$-st and the $3$-rd trucks. The sixth: choose $(L, R) = (2, 4)$, and select the $2$-nd and the $3$-rd trucks. ### Sample 2 See `2.in` and `2.ans` in the problem directory. This sample satisfies $n, m \le 18$. ### Sample 3 See `3.in` and `3.ans` in the problem directory. This sample satisfies $n, m \le 50$. ### Sample 4 See `4.in` and `4.ans` in the problem directory. This sample satisfies $n, m \le 400$. ### Sample 5 See `5.in` and `5.ans` in the problem directory. This sample satisfies $n, m \le 3000$. ### Sample 6 See `6.in` and `6.ans` in the problem directory. This sample satisfies special property A. ### Sample 7 See `7.in` and `7.ans` in the problem directory. This sample satisfies $n, m \le 200000$. ### Subtasks | Test Point ID | $n \le$ | $m \le$ | Special Property | |:-------------:|:---------:|:---------:|:----------------:| | $1$ | $18$ | $18$ | None | | $2$ | ^ | ^ | ^ | | $3$ | ^ | ^ | ^ | | $4$ | $50$ | $50$ | ^ | | $5$ | ^ | ^ | ^ | | $6$ | $400$ | $400$ | ^ | | $7$ | ^ | ^ | ^ | | $8$ | $3000$ | $3000$ | ^ | | $9$ | ^ | ^ | ^ | | $10$ | ^ | ^ | ^ | | $11$ | ^ | ^ | ^ | | $12$ | ^ | ^ | ^ | | $13$ | $200000$ | $200000$ | A | | $14$ | ^ | ^ | ^ | | $15$ | ^ | ^ | ^ | | $16$ | ^ | ^ | None | | $17$ | ^ | ^ | ^ | | $18$ | ^ | ^ | ^ | | $19$ | ^ | ^ | ^ | | $20$ | ^ | ^ | ^ | Special property A: It is guaranteed that for any two trucks, their fertilization ranges do not contain each other. That is, for any $1 \le i < j \le m$, either $l_i < l_j, r_i < r_j$ or $l_i > l_j, r_i > r_j$. Translated by ChatGPT 5