不知道贴的对不对，如果贴错了请别见笑。

下文来源：http://www.matrix67.com/blog/archives/1013
(作者是北大中文系的)

假设有一个长度为N的数组A_i，里面的每个数都不一样。但是呢，你不知道数组里的数是多少。给出若干个形如“从A_i到A_j中的最小值是x”的命题，问你第一个和前面有矛盾的命题在哪里。例如，给你四个命题：A_1到A_10的最小值是7，A_5到A_19的最小值是8，A_3到A_12的最小值是5，A_11到A_15的最小值是4。第三句话显然是错的，否则前两个区间中至少有一个的最小值也达到了5。
    这个题难就难在，我们需要挖掘出“矛盾”的本质。究竟每一条命题给我们带来了什么信息呢？假设我告诉你，A_1到A_10的最小值是7，你仍旧不能推断出任何一个数，但有两点是肯定的：第一，这10个数里有一个数字7；第二，这里面的每个数都不能小于7。假设我们再给出一个A_5到A_19的最小值是8呢？此时，我们得知A_5到A_19里面有一个8，并且A_5到A_19的所有数都不小于8。注意！此时从A_5到A_10这一段中的数字下界升级了！由此得到启发，这些条件给出的信息说穿了就是每个位置可能出现的数的下界，它就是覆盖它的那些区间中的最大值。我们可以把区间端点排序，从左到右扫描一遍，用堆不断更新当前的最大值。在确定完每个位置可能的最小数后，我们开始寻找一个满足这些条件的解。由于数组中没有相同的数，因此对于所有回答“最小值为x”的区间，x必需出现在它们的交集中。如果这个交集为空，或者交集里面所有的位置（因下界过大）都不能取这个数，那么我们就可以肯定地说这一组条件是有矛盾的。如果我们顺利地给每个区间都安排好最小值所在位置，这立即说明了该组条件没有矛盾，因为我把其它那些没确定下来的位置取到无穷大，满足全部条件的数组就构造出来了。于是，我们有了一个O(nlogn)判断一组命题是否有矛盾的算法。
    这个题有趣就有趣在，上述算法虽然高效，但却只能判断命题组是否矛盾，不能检测矛盾首次出现的位置；而在线判断命题是否矛盾（一个命题一个命题地往里面加）反而要慢些。于是呢，二分答案就派上用场了：二分前面的无冲突命题的最大长度，然后用上面的O(nlogn)算法来判断看是不是有矛盾。