20pts求调玄关
查看原帖
20pts求调玄关
933802
ICU152_lowa_IS8楼主2023/12/31 19:11
#include<bits/stdc++.h>
#define eps 0.0000000001
using namespace std;
struct tree{
	int val,minn;
}tree[400005];
int a[100005],ap=0;
inline int ls(int p){
	return p<<1;
}
inline int rs(int p){
	return p<<1|1;
}
inline void pushup(int p){
	tree[p].val=tree[ls(p)].val+tree[rs(p)].val;
	tree[p].minn=min(tree[ls(p)].val,tree[rs(p)].val);
}
inline void build(int l,int r,int p){
	if(l==r){
		tree[p].val=a[l];
		tree[p].minn=a[l];
		return;
	}
	int mid=l+r>>1;
	build(l,mid,ls(p));
	build(mid+1,r,rs(p));
	pushup(p);
}
inline int querysum(int l,int r,int ql,int qr,int p){
	if(l>qr||r<ql)return 0;
	if(qr>=r&&ql<=l){
		return tree[p].val;
	}
	if(l==r)return tree[p].val;
	int mid=l+r>>1;
	return querysum(l,mid,ql,qr,ls(p))+querysum(mid+1,r,ql,qr,rs(p));
}
inline int querymin(int l,int r,int ql,int qr,int p){
	if(l>qr||r<ql)return INT_MAX;
	if(qr>=r&&ql<=l){
		return tree[p].minn;
	}
	if(l==r)return tree[p].minn;
	int mid=l+r>>1;
	return min(querymin(l,mid,ql,qr,ls(p)),querymin(mid+1,r,ql,qr,rs(p)));
}
int main(){
	int n;
	cin>>n;
	for(int i=1;i<=n;i++){
		cin>>a[i];
	}
	build(1,n,1);
	double ans=0;
	for(int i=1;i<=n-2;i++){
		double f=(querysum(1,n,i+1,n,1)-querymin(1,n,i+1,n,1))*1.0/(n-i-1);
		if(f-eps<ans&&f+eps>ans){
			a[++ap]=i;
		}
		else if(f>ans+eps){
			ans=f;
			a[1]=i;
			ap=1;
		}
	}
	for(int i=1;i<=ap;i++){
		cout<<a[i]<<endl; 
	}
	return 0;
}
2023/12/31 19:11
加载中...