526互联

Codeforces 1696G - Fishingprince Plays With Array Again

发布时间 2023-07-20 13:01:03作者: tzc_wk

初读题目可以发现一些性质：

  • 每次操作会使整个序列的和减少至多 \(X+Y\)，因此 \(ans\ge\dfrac{\sum a_i}{X+Y}\)。
  • 对于两个不相邻位置 \(a_i,a_j(|i-j|>1)\)，每次操作最多使它们的和减少 \(\max(X,Y)\)。

然后你发现两个限制可以结合在一起使用，稍加思考可以得到一个比较普适的结论：

  • 对于任意序列 \(d\)，如果满足 \(d_i\in\{0,\dfrac{1}{X+Y},\dfrac{1}{\max(X,Y)}\}\)，且 \(\forall d_i=\dfrac{1}{\max(X,Y)}\},d_{i-1}=d_{i+1}=0\)，那么有 \(ans\ge\sum\limits_{i=1}^na_id_i\)。

这样的下界是否就一定能取到呢？答案是肯定的。证明需要线性规划对偶，这里不再赘述。

使用线段树维护矩阵乘法可以快速求解答案。

const int MAXN=2e5;
const double INF=1e18;
int n,qu,X,Y,a[MAXN+5];
struct mat{
	double a[3][3];
	mat(){for(int i=0;i<3;i++)for(int j=0;j<3;j++)a[i][j]=-INF;}
	friend mat operator *(const mat &X,const mat &Y){
		mat ret;
		for(int i=0;i<3;i++)for(int j=0;j<3;j++)for(int k=0;k<3;k++)
			chkmax(ret.a[i][j],X.a[i][k]+Y.a[k][j]);
		return ret;
	}
}trs;
struct node{int l,r;mat v;}s[MAXN*4+5];
void build(int k,int l,int r){
	s[k].l=l;s[k].r=r;
	if(l==r){
		s[k].v.a[0][0]=0;s[k].v.a[1][1]=1.0*a[l]/(X+Y);
		s[k].v.a[2][2]=1.0*a[l]/Y;return;
	}int mid=l+r>>1;build(k<<1,l,mid);build(k<<1|1,mid+1,r);
	s[k].v=s[k<<1].v*trs*s[k<<1|1].v;
}
void modify(int k,int p,int v){
	if(s[k].l==s[k].r){
		s[k].v.a[0][0]=0;s[k].v.a[1][1]=1.0*v/(X+Y);
		s[k].v.a[2][2]=1.0*v/Y;return;
	}int mid=s[k].l+s[k].r>>1;
	if(p<=mid)modify(k<<1,p,v);else modify(k<<1|1,p,v);
	s[k].v=s[k<<1].v*trs*s[k<<1|1].v;
}
mat query(int k,int l,int r){
	if(l<=s[k].l&&s[k].r<=r)return s[k].v;int mid=s[k].l+s[k].r>>1;
	if(r<=mid)return query(k<<1,l,r);else if(l>mid)return query(k<<1|1,l,r);
	else return query(k<<1,l,mid)*trs*query(k<<1|1,mid+1,r);
}
int main(){
	scanf("%d%d%d%d",&n,&qu,&X,&Y);if(X>Y)swap(X,Y);
	for(int i=1;i<=n;i++)scanf("%d",&a[i]);
	for(int i=0;i<3;i++)for(int j=0;j<3;j++)if((i!=2&&j!=2)||i==0||j==0)trs.a[i][j]=0;
	build(1,1,n);
	while(qu--){
		int opt;scanf("%d",&opt);
		if(opt==1){
			int p,v;scanf("%d%d",&p,&v);
			modify(1,p,v);
		}else{
			int l,r;scanf("%d%d",&l,&r);mat tt=query(1,l,r);double mx=-INF;
			for(int i=0;i<3;i++)for(int j=0;j<3;j++)chkmax(mx,tt.a[i][j]);
			printf("%.10lf\n",mx);
		}
	}
	return 0;
}