OpenJudge

1049:CZP1607小X与煎饼达人

总时间限制:
10000ms
单个测试点时间限制:
1000ms
内存限制:
262144kB
描述

玩着玩着小X觉得有点饿了,他想出门买些吃的。刚刚走出大门,小X就看到有位大叔在做煎饼,而且做法十分有趣。

只见此人将n块煎饼排成一排,手持一把大铲,将煎饼铲得上下翻飞,煞是好看。

小X顿时食指大动,赶紧走上前去细细打量,发现此人做煎饼还十分的讲究,在做的过程中,大叔每次会将从第x块煎饼开始到第y块煎饼结束的这y-x+1块煎饼全部翻个个儿(正面翻到反面,反面翻到正面)。

而他每次会选择不同的区间(区间是指连续的一段煎饼3,4,5,6四块煎饼用区间[3,6] 表示)来翻这些煎饼。每块煎饼都有正反两面,开始时这些煎饼都是反面朝上。

此人一共翻了m次煎饼,看得小X眼花缭乱。 但是小X很想知道这n块煎饼到最后一共有多少块是正面朝上的,于是他只好求助于你了。

输入
第一行包含两个用空格隔开的正整数表示n和m。

接下来m行每行两个用空格隔开的正整数x和y,表示每次将区间[x,y] 中的 y-x+1块煎饼翻个个儿。

开始时这n块煎饼都是反面朝上(提示:可以用0表示煎饼的反面,1 表示煎饼的正面)
输出
输出仅有一行包含一个整数ans,表示最后有ans块煎饼是正面朝上的。
样例输入
10 5
1 8
5 6
1 9
3 8
2 7
样例输出
5
提示
【数据范围】

1 ≤ n ≤ 1000000,1 ≤ m ≤ 100000,1 ≤ x ≤ y ≤ n
【样例解释】

共有 10 块煎饼, 开始时状态为“反反反反反反反反反反”, 第一次操作将区间[1,8] 的煎饼翻个身,状态变成“ 正正正正正正正正反反”, 红色表示翻的区间。 第二次操作将区间[5,6] 的煎饼翻个身, 状态变成“正正正正反反正正反反”。 第三次操作将区间[1, 9] 的煎饼翻个身, 状态变成“ 反反反反正正反反正反”。 第四次操作将区间[3,8] 的煎饼翻个身, 状态变成“反反正正反反正正正反”。 第五次操作将区间[2,7] 的煎饼翻个身, 状态变成“反正反反正正反正正反”。最后共有 5 块煎饼正面朝上。

每个题目的视频讲解会逐步推出,请访问
http://i.youku.com/oiclub

全局题号
14436
添加于
2017-04-08
提交次数
63
尝试人数
30
通过人数
18