题意是给你一个长度为N的数组，你在每个长度大于等于K的连续区间里，取出第K大的数，组成一个新数组。问新数组中第M大的数是什么。

 

这道题最最重要的就是，尺取法可以求出第k大的数大于等于x的区间数。

为什么可以呢？假设我们尺取法已经取到了K个大于等于x的数的区间，当我们右指针往后移动的时候，新加入的数对这个区间产生的贡献无非两种：

1. 使第K大的数变大

2. 第K大的数不变

我们发现这两种贡献都是不影响我们定义的第k大的数大于等于x区间。于是我们就只需要不断计算每个左区间开始的，符合条件的区间数即可。

 

之后我们讲一讲二分是怎么二分的。首先给出答案，二分这个X是什么。即二分答案。

为什么可以呢？首先我们发现，当X变大的时候，符合条件的区间数会减小，而X变小的时候，符合条件的区间数会变大。这个条件是满足单调性的。所以可以二分。

那么怎么二分呢？我们需要找的是，新数组中第M个数，这就说明大于X的区间起码要有M-1个，大于等于X的区间起码要有M个。

于是我们就得到了二分最终位置。

下面给出AC代码，注意有一个坑点就是M有可能是大于int的。