题目描述

一个序列的极差定义为此序列中最大值和最小值之差。给你一个长度为n的序列a_1..an，你需要选出k个极差均不小于X且长度为L(L>=1)的不同连续子序列。a{i1},...a{i1+L-1}, a{i2},...a{i2+L-1}, ... , a{ik},...a_{ik+L-1}, (i1..ik)互不相同。

要求能满足条件的最大的X，在满足X最大的情况下，再让L最小

输入格式:第一行一个整数T，表示测试数据组数

每组数据中：第一行两个整数n,k；第二行n个整数a_1,a_2,...,a_n

100%的数据，1<=T<=10, 1<=k<=n<=100000, -1e9<=a<=1e9

蒟蒻写了一个二分答案，答案内尺取+单调队列+差分，复杂度应该是O(log(1e9) n t)，但是只过了70分。

大佬们，有没有复杂度更优秀的做法？如果没有能不能帮我优化一下常数？

70分的代码:

#include<bits/stdc++.h>
using namespace std;
long long ai[110001];
int n;
int k;
long long cf[110001];
int ok(long long x){
	memset(cf,0,sizeof(cf));
	int ptr=0;
	static int d[200001];
	static int d2[200001];
	int lr=1,rr=0;
	int lr1=1,rr1=0;
	for(int i=1;i<=n;i++){
		if(ptr<i){
			ptr=i;
			while(lr<=rr and ai[d[rr]]<= ai[i])rr--;
			d[++rr]=i;
			while(lr1<=rr1 and ai[d2[rr1]]>= ai[i])rr1--;
			d2[++rr1]=i;
		}
		while(ptr <=n and ai[d[lr]]-ai[d2[lr1]] < x){
			ptr++;
			while(lr<=rr and ai[d[rr]]<= ai[ptr])rr--;
			d[++rr]=ptr;
			while(lr1<=rr1 and ai[d2[rr1]]>= ai[ptr])rr1--;
			d2[++rr1]=ptr;
		}
		cf[ptr-i+1]++,cf[n-i+2]--;
		while(lr<=rr and d[lr]<=i)lr++;
		while(lr1<=rr1 and d2[lr1]<=i)lr1++;
	}
	int sm=0;
	for(int i=1;i<=n;i++){
		sm+=cf[i];
		if(sm>=k)return i;
	}
	return -1;
}
inline int read()
{
	int s=0,w=1;
	char ch=getchar();
	while(!isdigit(ch))
	{
		if(ch=='-') w=-1;
		ch=getchar();
	}
	while(isdigit(ch)) 
	{
		s=s*10+ch-'0',ch=getchar();
	}
	return s*w;
}
int main(){
	freopen("select.in","r",stdin);
	freopen("select.out","w",stdout);
	int t;
	cin>>t;
	for(int j=1;j<=t;j++){
		//clock_t ss,ee;
		//ss=clock();
		cin>>n>>k;
        long long minn=9999999999,maxx=-9999999999;
		for(int i=1;i<=n;i++)ai[i]=read(),minn=min(minn,ai[i]),maxx=max(maxx,ai[i]);
		long long l=0,r=maxx-minn;
		long long ans=0,res=0,ans2=0;
		while(l<=r){
			long long mid=(l+r)>>1;
			res=ok(mid);	
			//cout<<mid<<endl;
			if(res==-1)r=mid-1;
			else l=mid+1,ans=res,ans2=mid;
		}
		cout<<ans2<<" "<<ans<<endl;
		//ee=clock();
	//	cout<<(double)(ee-ss)/CLOCKS_PER_SEC;
	}
	return 0;
}