本来就一道自闭题的，但是第二道莫名其妙把我写自闭了，
明明本地是对的，为什么交上去是错的明明样例本地过了，为什么交上去过不了，而且我按照原来的代码重写了一边，竟然又可以过了。。。。更恐怖的是，我不是第一次遇到这种事情了。。。。。。上次一摸一样的代码运行出不一样的结果的原因我到现在也不知道emmmmm
不过这次主要自闭的还是 HDU-6231 。
题意是这样的
给你一个数组 A，让你将长度大于 k 的 A 数组的所有子区间中的第k大数找出来放入数组 B 中，然后输出其中的第 m 大数。
这个题一开始思考方向就是错的，数据结构显然不行，因为只有线段树可用但是无法合并，其实仔细算一下就会发现，已知 A 数组范围是 1e5 的，如果将 k=1 时的 B 数组全算出来，那么 B 数组的大小将会达到近 1e10 ，也就是说，想靠什么方法将 B 求出来的方法是一定不行的emmmmmm，这么长时间没发现我也是菜。
然后就是算法的问题了，其实不难发现，我们最终要的答案就只是B中的第m大数，所以我们没必要将 B 所有的都算出来，算出比大于等于答案的所有的数就可以了。
但是这也不容易，还有一个不难发现的地方是，我们并不确定答案的值，而且，存在可以确定一个数一定不是答案的条件：如果大于等于 x 的所有数做第 k 大数的子区间个数小于 m ，x 就一定不可能是答案，而且，比 x 大的数也一定不是答案。
这样，我们就可以写出 check 函数，然后每次去掉一半的区间，这不就是二分吗。。。。
然后就是最大的难点，如何写 check 函数来找出子区间的个数，这就用到了尺取法。
这需要用到两个指针，我们用 l , r 来表示，开始 l , r 都指向开头，然后 r 开始向后扫，并用 num 记录 [ l , r ] 区间中大于等于 x 的元素的个数，当个数等于 k 后，则 [ l , r ~ n ] 的所有区间的第 k 大数都大于等于 x ，然后把这些区间的个数加到 sum 上。下面 r 再向后扫， r 每向后扫一位都会使区间个数增加，直到扫到第一个大于等于 x 的数，然后把这个数去掉，即 num 减一。
这样扫到最后，得到的 sum 就是所需要的子区间的个数。
#include<bits/stdc++.h>
#define ll long long
using namespace std;
const int N=1e5+5,M=998244353;
ll a[N];
ll b[N];
ll n,k,m;
bool check(ll x)
{
ll num=0;
int l=1;
int r=1;
ll sum=0;
while(r<=n+1){
if(num<k){
if(a[r]>=x){
num++;
}
r++;
}
else {
sum+=n-r+2;
if(a[l]>=x){
num--;
}
l++;
}
}
if(sum>=m){
return true;
}
else return false;
}
int main()
{
ios::sync_with_stdio(false);
int t;
cin>>t;
while(t--){
cin>>n>>k>>m;
for(int i=1;i<=n;i++)
{
cin>>a[i];b[i]=a[i];
}
int l=1,r=n;
int mid;
sort(b+1,b+n+1);
ll ans=0;
while(l<=r){
mid=l+((r-l)>>1);
ll x=b[mid];
if(check(x)){
ans=x;
l=mid+1;
}
else r=mid-1;
}
cout<<ans<<endl;
}
}
真的惨啊，二分还是不熟练，当然也可能是因为昨天喝了三杯咖啡的原因，晚上失眠，上午又去打球，中午又没有睡觉，下午头疼的一匹，精神状态也有些不正常。
不过主要原因还是菜啊。。。。。