B18 实践-5 堆叠草堆

题目描述

佩奇对她自己最近在农场周围的恶作剧感到抱歉，于是她同意帮助猪爷爷堆叠新送达的一批干草捆。 开始时有$N$($N$是奇数)个空草堆，标记为 $1...N$ 。猪爷爷 将会给 佩奇包含 $K$ 条指令的序列，每条指令的格式为 A B，表示 佩奇应该在草堆 $[A,B]$ 中每一个草堆顶部新放一捆干草。例如，如果 佩奇听到指令 10 13，那么她应该在草堆 $10,11,12$ 和 $13$ 上各新放一捆干草。 在 佩奇完成了 猪爷爷 的所有指令后，猪爷爷 想要知道 $N$ 个草堆高度的中位数——也就是说，所有草堆排序后中央草堆(由于 $N$ 是奇数，这个草堆是唯一的)的高度。请帮助 佩奇确定 猪爷爷问题的答案。

输入格式

第 $1$ 行：两个被空格分隔的整数$N$和$K$。 第 $2\sim K+1$ 行：每行包含一条 猪爷爷 的指令，其格式为两个被空格分隔的整数 $A$ 和 $B$。

输出格式

输出共一行一个整数， 佩奇完成所有指令后草堆高度的中位数。

样例输入

7 4
5 5
2 4
4 6
3 5

样例输出

1

样例说明

有 $N=7$ 个草堆，猪爷爷 给出了 $K=4$ 条指令。第一条指令要求增加草堆 $5$ 的干草捆，第二条指令要求增加草堆 $2..4$ 的干草捆，等等。

佩奇完成任务后，草堆的高度为 $0,1,2,3,3,1,0$ 。高度的中位数是$1$，因为 $1$ 是排序后结果 $0,0,1,1,2,3,3$ 的中间数。

数据范围

对于 $60\%$ 的数据：$1\le N \le 1000$，$1\le K\le 1000$。 对于 $100\%$ 的数据：$1\le N \le 10^5$，$1\le K\le 10^5$，$1 \le A \le B$，$N$ 为奇数。