记录编号	319134	评测结果	AAAAAAAAAA
题目名称	2382.[HZOI 2016]最佳序列	最终得分	100
用户昵称	AntiLeaf	是否通过	通过
代码语言	C++	运行时间	0.397 s
提交时间	2016-10-10 14:40:34	内存使用	1.67 MiB

#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
const int maxn=33010,num[]={1,2,4,8,16,32,64,128,256,512,1024,2048,4096,8192,16384,32768};
long double qmin(int,int);
int n,m,l,r;
long long a[maxn];
long double b[maxn],mn[maxn<<1],L,R,ans,tmp;
int main(){
	freopen("bestseq.in","r",stdin);
	freopen("bestseq.out","w",stdout);
	scanf("%d%d%d",&n,&l,&r);
	m=n;
	n=*lower_bound(num,num+16,n+3);
	for(int i=1;i<=m;i++)scanf("%lld",&a[i]);
	L=-1e10;R=1e10;
	while(R-L>1e-6){
		ans=(L+R)/2.0;
		tmp=-1e30;
		b[0]=0.0;
		for(int i=1;i<=m;i++)b[i]=mn[i+n+1]=b[i-1]+(double)a[i]-ans;
		mn[n]=mn[n+1]=0.0;
		for(int i=m+n+2;i<(n<<1);i++)mn[i]=1e30;
		for(int i=n-1;i;i--)mn[i]=min(mn[i<<1],mn[i<<1|1]);
		for(int i=l;i<=m;i++)tmp=max(tmp,b[i]-qmin(i-r+1,i-l+1));
		if(tmp>0)L=ans;
		else R=ans;
	}
	printf("%.4lf",(double)L);
	fclose(stdin);
	fclose(stdout);
	return 0;
}
long double qmin(int l,int r){
	if(l<1)l=1;
	long double ans=1e30;
	for(l=l+n-1,r=r+n+1;l^r^1;l>>=1,r>>=1){
		if(~l&1)ans=min(ans,mn[l^1]);
		if(r&1)ans=min(ans,mn[r^1]);
	}
	return ans;
}
/*
3 2 3
6 2 8
Answer:
5.3333
*/
/*
二分答案ans，然后求解有限制的最大连续和是否<=0即可。
max{s[i]-RMQ_min(i-r,i-l)}即为最大连续和。
懒得写单调队列了...写的zkw...
把下标搞成0~n-1，一个节点对应的叶子就是x+n。
*/