{"trustable":true,"prependHtml":"\u003cstyle type\u003d\"text/css\"\u003e\n #problem-body \u003e pre {\n display: block;\n padding: 9.5px;\n margin: 0 0 10px;\n font-size: 13px;\n line-height: 1.42857143;\n word-break: break-all;\n word-wrap: break-word;\n color: #333;\n background: rgba(255, 255, 255, 0.5);\n border: 1px solid #ccc;\n border-radius: 6px;\n }\n\u003c/style\u003e\n","sections":[{"title":"","value":{"format":"HTML","content":"\u003cdiv id\u003d\"problem-body\"\u003e\n\t\u003cp\u003e最近在农场闹了不少小动作,贝西感到很抱歉,于是她答应帮助约翰农夫堆放一批新运来的干草。\u003c/p\u003e\n\n\u003cp\u003e她开始时有 N(1 \u0026lt;\u003d N \u0026lt;\u003d 1,000,000, N 为奇数)个空栈,编号为 1..N。\n约翰农夫给了她一系列 K 条指令(1 \u0026lt;\u003d K \u0026lt;\u003d 25,000),每条指令的形式为“A B”,表示贝西应该在 A..B 范围内的每个栈顶部添加一捆新的干草。例如,如果贝西被告知“10 13”,那么她应该在第 10、11、12、13 号栈中各添加一捆干草。\u003c/p\u003e\n\n\u003cp\u003e在贝西按照约翰农夫的指令堆放完干草后,约翰农夫想知道 N 个栈的中位数高度——也就是说,如果栈按照排序顺序排列,那么中间的栈的高度是多少(方便起见,N 是奇数,因此这个栈是唯一的)。请帮助贝西确定约翰农夫问题的答案。\u003c/p\u003e\n\n\u003ch3\u003e输入\u003c/h3\u003e\n\u003cul\u003e\n\u003cli\u003e第 1 行:两个以空格分隔的整数 N 和 K。\u003c/li\u003e\n\u003cli\u003e第 2 行至第 1+K 行:每行包含一条约翰农夫的指令,形式为两个以空格分隔的整数 A 和 B(1 \u0026lt;\u003d A \u0026lt;\u003d B \u0026lt;\u003d N)。\u003c/li\u003e\n\u003c/ul\u003e\n\n\u003ch3\u003e输出\u003c/h3\u003e\n\u003cul\u003e\n\u003cli\u003e第 1 行:贝西完成指令后栈的中位数高度。\u003c/li\u003e\n\u003c/ul\u003e\n\n\u003ch3\u003e样例\u003c/h3\u003e\n\u003cdiv\u003e\u003ctable class\u003d\"vjudge_sample\"\u003e\n\u003cthead\u003e\n \u003ctr\u003e\n \u003cth\u003eInput\u003c/th\u003e\n \u003cth\u003eOutput\u003c/th\u003e\n \u003c/tr\u003e\n\u003c/thead\u003e\n\u003ctbody\u003e\n \u003ctr\u003e\n \u003ctd\u003e\u003cpre\u003e7 4\r\n5 5\r\n2 4\r\n4 6\r\n3 5\r\n\r\n\u003c/pre\u003e\u003c/td\u003e\n \u003ctd\u003e\u003cpre\u003e1\u003c/pre\u003e\u003c/td\u003e\n \u003c/tr\u003e\n\u003c/tbody\u003e\n\u003c/table\u003e\n\u003c/div\u003e\n\n\u003ch3\u003e样例说明\u003c/h3\u003e\n\u003cp\u003e有 N\u003d7 个栈,约翰农夫发出 K\u003d4 条指令。第一条指令是在第 5 号栈添加一捆干草,第二条是在第 2..4 号栈添加干草,依此类推。\u003c/p\u003e\n\n\u003cp\u003e贝西完成后,栈的高度分别为 0, 1, 2, 3, 3, 1, 0。中位数栈高度为 1,因为 1 是排序顺序 0, 0, 1, 1, 2, 3, 3 中的中间元素。\u003c/p\u003e\n\n\u003c/div\u003e"}}]}