Beautiful fountains rows

题意翻译

给你一个 $ n $ 行 $ m $ 列的矩阵 $ S $ ,第 $ i $ 行中,只有 $ l_i $ 到 $ r_i $ 的方格是 $ 1 $ ,其它位置均为 $ 0 $ .换句话说,即 $ s_{i,j}=1 $ $(1\leq i\leq n,l_i\leq j\leq r_i)$ ,剩余位置为 $ 0 $ . 现在我们规定, $ (a,b) $ 是一个好点对,当且仅当: - $\sum_{i=1}^n\sum_{j=a}^bs_{i,j}>0$. - 对于第 $ i $ 行, $\sum_{j=a}^bs_{i,j}$为 $ 0 $ 或奇数. 求出所有好点对 $ (a,b) $ 的 $ b-a+1 $的总和.

题目描述

Butler Ostin wants to show Arkady that rows of odd number of fountains are beautiful, while rows of even number of fountains are not. The butler wants to show Arkady $ n $ gardens. Each garden is a row of $ m $ cells, the $ i $ -th garden has one fountain in each of the cells between $ l_{i} $ and $ r_{i} $ inclusive, and there are no more fountains in that garden. The issue is that some of the gardens contain even number of fountains, it is wrong to show them to Arkady. Ostin wants to choose two integers $ a<=b $ and show only part of each of the gardens that starts at cell $ a $ and ends at cell $ b $ . Of course, only such segments suit Ostin that each garden has either zero or odd number of fountains on this segment. Also, it is necessary that at least one garden has at least one fountain on the segment from $ a $ to $ b $ . Help Ostin to find the total length of all such segments, i.e. sum up the value $ (b-a+1) $ for each suitable pair $ (a,b) $ .

输入输出格式

输入格式

The first line contains two integers $ n $ and $ m $ ( $ 1<=n,m<=2·10^{5} $ ) — the number of gardens and the length of each garden. $ n $ lines follow. The $ i $ -th of these lines contains two integers $ l_{i} $ and $ r_{i} $ ( $ 1<=l_{i}<=r_{i}<=m $ ) — the bounds of the segment that contains fountains in the $ i $ -th garden.

输出格式

Print one integer: the total length of all suitable segments.

输入输出样例

输入样例 #1

1 5
2 4

输出样例 #1

23

输入样例 #2

3 6
2 4
3 6
4 4

输出样例 #2

19

说明

In the first example the following pairs suit Ostin: $ (a,b) $ : $ (1,2) $ , $ (1,4) $ , $ (1,5) $ , $ (2,2) $ , $ (2,4) $ , $ (2,5) $ , $ (3,3) $ , $ (4,4) $ , $ (4,5) $ . In the second example the following pairs suit Ostin: $ (a,b) $ : $ (1,2) $ , $ (1,5) $ , $ (2,2) $ , $ (2,5) $ , $ (3,3) $ , $ (4,4) $ , $ (4,6) $ , $ (5,5) $ , $ (6,6) $ .