{"trustable":true,"sections":[{"title":"","value":{"format":"HTML","content":"Chris有限公司正在准备一种新的排序硬件,称为Maximizer。Maximizer有n个输入,编号从1到n。每个输入代表一个整数。Maximizer有一个输出,表示Maximizer输入中的最大值。\u003cbr\u003e\u003cbr\u003eMaximizer实现为一系列排序器 Sorter(i1, j1), ... , Sorter(ik, jk) 的管道。每个排序器有n个输入和n个输出。Sorter(i, j)对输入i, i+1,..., j上的值进行非递减排序,并让其他输入保持不变。最后一个排序器的第n个输出是Maximizer的输出。\u003cbr\u003e\u003cbr\u003e一名实习生(前ACM选手)观察到,有些排序器可以从管道中排除,Maximizer仍然可以产生正确的结果。给定的排序器序列中,仍然能为所有可能的输入值组合产生正确结果的最短子序列的长度是多少?\u003cbr\u003e\u003cbr\u003e任务\u003cbr\u003e编写一个程序:\u003cbr\u003e\u003cbr\u003e读取Maximizer的描述,即管道中初始排序器的序列,\u003cbr\u003e计算仍然能为所有可能输入数据产生正确结果的初始排序器序列的最短子序列的长度,\u003cbr\u003e输出结果。\u003cbr\u003e"}},{"title":"输入","value":{"format":"HTML","content":"输入的第一行包含两个整数n和m(2 \u0026lt;\u003d n \u0026lt;\u003d 50000,1 \u0026lt;\u003d m \u0026lt;\u003d 500000),用一个空格分隔。整数n是输入的数量,整数m是管道中排序器的数量。接下来的m行描述了初始排序器的序列。第k行包含第k个排序器的参数:两个整数ik和jk(1 \u0026lt;\u003d ik \u0026lt; jk \u0026lt;\u003d n),用一个空格分隔。"}},{"title":"输出","value":{"format":"HTML","content":"输出仅包含一行,包含一个整数,等于仍然能为所有可能数据产生正确结果的初始排序器序列的最短子序列的长度。"}},{"title":"示例","value":{"format":"HTML","content":"\u003ctable class\u003d\u0027vjudge_sample\u0027\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\u003e40 6\r\n20 30\r\n1 10\r\n10 20\r\n20 30\r\n15 25\r\n30 40\r\n\u003c/pre\u003e\u003c/td\u003e\n \u003ctd\u003e\u003cpre\u003e4\r\n\u003c/pre\u003e\u003c/td\u003e\n \u003c/tr\u003e\n\u003c/tbody\u003e\n\u003c/table\u003e"}},{"title":"提示","value":{"format":"HTML","content":"数据量巨大,建议使用scanf。"}}]}