#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,8]
正 正 正 正 正 正 正 正 反 反
- 翻区间
[5,6]
正 正 正 正 反 反 正 正 反 反
- 翻区间 [1,9]`
反 反 反 反 正 正 反 反 正 反
- 翻区间
[3,8]
反 反 正 正 反 反 正 正 正 反
- 翻区间
[2,7]
反 正 反 反 正 正 反 正 正 反
最终正面朝上的煎饼共有 5 块。
数据范围:
-
30% 的数据: 1 ≤ n, m ≤ 100,1 ≤ x ≤ y ≤ n
-
30% 的数据: 1 ≤ n ≤ 1,000,000,1 ≤ m ≤ 100,000,x = 1,1 ≤ y ≤ n
-
40% 的数据: 1 ≤ n ≤ 1,000,000,1 ≤ m ≤ 100,000,1 ≤ x ≤ y ≤ n