#Pusaco12janbronze2. 干草堆

    ID: 672 传统题 1000ms 256MiB 尝试: 0 已通过: 0 难度: 提高 上传者: 标签>bronzeusaco赛制:OI来源:wyfoj http://127.0.0.1差分排序

干草堆

干草堆

题目描述

贝茜为最近在农场附近造成的种种灾难感到难过,她同意帮助农场主约翰把一批干草捆起来。一开始有N(1 <= N <= 1,000,000, N 是奇数)个空堆,编号为1..N。农场主约翰给出了K (1 <= K <= 25,000)条指令,格式为“A B"的形式,意思是贝茜要添加一包新的干草到范围为A..B的干草堆顶。例如,如果贝茜的指令是”10 13“,那么她要给10,11,12和13这些干草堆添加一包干草。在贝茜完成了所有干草堆的指令后,农场主约翰要知道N堆干草的中间高度是多少——这就意味着需要对高度进行排序(为了方便,N是奇数,所以中间的高度是独一无二的)。请帮助贝茜确定农场主约翰问题的答案。

输入格式

第1行:两个空格隔开的整数,N K。第2..1+K行:每行包含一条FJ的指令,为两个空格隔开的整数A B (1 <= A <= B <= N)。

输出格式

第1行:贝茜完成指令后干草堆的中间高度。

数据范围

(原站未提供,导入后需人工补齐)

样例

7 4
5 5
2 4
4 6
3 5
1

提示

输入描述:这里有N=7堆干草,FJ有K=4条指令。第1条指令是添加一包干草到5号堆,第2条指令是添加干草到2..4号堆,依此类推。

输出描述:在贝茜完成后,干草堆的高度分别是0,1,2,3,3,1,0。中间高度是1,因为1在排序后0,0,1,1,2,3,3的中间位置。