#4404. 翻煎饼

翻煎饼

题目描述:

小 X 出门买吃的时,看到一位大叔在做煎饼。大叔把 $n$ 块煎饼排成一排,每块煎饼都有正反两面,初始时都是反面朝上。

大叔每次会将从第 $x$ 块煎饼到第 $y$ 块煎饼的整段煎饼翻面(正面翻到反面,反面翻到正面)。他一共翻了 $m$ 次,每次翻的区间可能不同。

请你计算最终有多少块煎饼是正面朝上的。


输入格式:

  • 第一行包含两个整数 $n$ 和 $m$,分别表示煎饼数量和翻煎饼次数。
  • 接下来 $m$ 行,每行包含两个整数 $x$ 和 $y$,表示一次翻煎饼操作,将区间 $[x, y]$ 中的所有煎饼翻面。

输出格式:

  • 输出一个整数,表示最终正面朝上的煎饼块数。

样例输入:

10 5
1 8
5 6
1 9
3 8
2 7

样例输出:

5

样例解释:

共有 10 块煎饼,开始时状态为:

反 反 反 反 反 反 反 反 反 反

操作过程如下(用“正”表示正面,“反”表示反面):

  1. 翻区间 [1,8]
正 正 正 正 正 正 正 正 反 反
  1. 翻区间 [5,6]
正 正 正 正 反 反 正 正 反 反
  1. 翻区间 [1,9]`
反 反 反 反 正 正 反 反 正 反
  1. 翻区间 [3,8]
反 反 正 正 反 反 正 正 正 反
  1. 翻区间 [2,7]
反 正 反 反 正 正 反 正 正 反

最终正面朝上的煎饼共有 5 块。


数据范围:

  1. 30% 的数据: 1 ≤ n, m ≤ 100,1 ≤ x ≤ y ≤ n

  2. 30% 的数据: 1 ≤ n ≤ 1,000,000,1 ≤ m ≤ 100,000,x = 1,1 ≤ y ≤ n

  3. 40% 的数据: 1 ≤ n ≤ 1,000,000,1 ≤ m ≤ 100,000,1 ≤ x ≤ y ≤ n