1538 - 小 X 与煎饼达人(flip)

题目描述

玩着玩着小 X 觉得有点饿了, 他想出门买些吃的。 刚刚走出大门,小 X 就看到有位大叔在做煎饼,而且做法十分有趣。 只见此人将 nn 块煎饼排成一排,手持一把大铲,将煎饼铲得上下翻飞, 煞是好看。 小 X 顿时食指大动, 赶紧走上前去细细打量, 发现此人做煎饼还十分的讲究,在做的过程中,大叔每次会将从第 xx 块煎饼开始到第 yy 块煎饼结束的这 yx+1y-x+1 块煎饼全部翻个个儿(正面翻到反面, 反面翻到正面)。而他每次会选择不同的区间(区间是指连续的一段煎饼,如 3,4,5,63, 4, 5, 6 四块煎饼用区间 [3,6][3, 6] 表示)来翻这些煎饼。每块煎饼都有正反两面, 开始时这些煎饼都是反面朝上。

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

输入

输入数据第一行包含两个用空格隔开的正整数表示 nnmm

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

开始时这 nn 块煎饼都是反面朝上(提示: 可以用 00 表示煎饼的反面,11 表示煎饼的正面)

输出

输出仅有一行包含一个整数 ansans , 表示最后有 ansans 块煎饼是正面朝上的。

样例

输入
复制

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

输出
复制

5
说明

【样例解释】

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

【数据范围】

对于 30%30\% 的数据, 1n,m1001 ≤ n,m ≤ 1001xyn1 ≤ x ≤ y ≤ n

对于另外 30%30\% 的数据, 1n10000001 ≤ n ≤ 10000001m1000001 ≤ m ≤ 100000x=1x = 1, 1yn1 ≤ y ≤ n

对于另外 40%40\% 的数据, 1n10000001 ≤ n ≤ 10000001m1000001 ≤ m ≤ 1000001xyn1 ≤ x ≤ y ≤ n

【来源】

常州市2016“信息与未来”夏令营选拔赛

来源

市赛 前缀和差分

标签
题目参数
时间限制 1 秒
内存限制 128 MB
提交次数 3045
通过人数 1492
金币数量 3 枚
难度 提高


上一题 下一题