Beautiful fountains rows
Contest: Playrix Codescapes Cup (Codeforces Round 413, rated, Div. 1 + Div. 2)
Difficulty rating: 3500
Tags: data structures

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 li and ri 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).

Input format:
The first line contains two integers n and m (1 ≤ n, m ≤ 2·105) — the number of gardens and the length of each garden.

n lines follow. The i-th of these lines contains two integers li and ri (1 ≤ li ≤ ri ≤ m) — the bounds of the segment that contains fountains in the i-th garden.

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

Constraints:
Time limit: 3.0 s
Memory limit: 256.0 MB

Note:
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).

Example input:
1 5
2 4

Example output:
23

Example input:
3 6
2 4
3 6
4 4

Example output:
19

Editorial:
Let's describe an O((n + m)2) solution first. Let's try all possible pairs (a, b) and check if they suit us. Let's try all values of a from 1 to m.
Let garden (x, y) denote a garden with fountains from x to y, and let's say that a garden bans a position x for a fixed a if there is non-zero even number of fountains on the segment [a, x], i.e. the pair (a, x) doesn't suit Ostin due to this garden.
Now there are two types of gardens we want consider: gardens of the first type start have form (x, y) where x < a, y ≥ a, and gardens of the second type have form (x, y) where a ≤ x ≤ y.
The gardens of the second type ban such positions equal to x + 1, x + 3, ..., and maybe y, y + 1, y + 2, ..., m if (y - x + 1) is even. These positions do not depend on a, we can keep an array that tells us how many gardens ban each position of b. Initially, we add 1 to all such positions for each garden, and we remove that 1 when the a passes beyond the left bound of that garden.
Let R be the set of right ends of all gardens of the first type. These gardens ban positions a + 1, a + 3, ..., x, where x is bounded by the maximum element in R. Also, if there is a value t in R such that (t - a + 1) is even, then all positions t, t + 1, t + 2, ..., m are banned as well. We're interested in the minimum value of t such that (t - a + 1) is even, so, we can keep two separate sets Reven and Rodd for even and odd values, and look for the minimum in one of them.
So, it's easy now to determine if a pair (a, b) is suitable or not. We can try all b, check is there is at least one fountain on [a, b] and add (b - a + 1) to the answer if the pair is suitable.
Let's improve the solution to $${ \mathcal { O } } ( n \log ( m + n ) )$$. We can note that each operation that changes banned positions for the second type gardens is a range query over odd or even numbers. So we can handle it with segment tree with range queries. Similarly, the gardens of the first type reduce non-banned positions of each parity to some segment, so we can do a range query to count the number of non-banned positions in the two trees described. The overall complexity is $${ \mathcal { O } } ( n \log ( m + n ) )$$.