2019.02.14 codechef Chef at the Food Fair（线段树+泰勒展开）

时间：2022-05-13 08:35:26

传送门

题意：现在有nnn个位置，每个位置上有一个值aia_iai​.

要求支持如下两种操作：

  1. 区间乘vvv
  2. 求区间的(1−ai)(1-a_i)(1−ai​)之积

思路：

考虑转换式子:

Ans=∏i=lr(1−ai)=e∑i=lrln(1−ai)Ans=\prod_{i=l}^r(1-a_i)=e^{\sum_{i=l}^rln(1-a_i)}Ans=∏i=lr​(1−ai​)=e∑i=lr​ln(1−ai​)

于是只需维护∑i=lrln(1−ai)\sum_{i=l}^rln(1-a_i)∑i=lr​ln(1−ai​)

把这个式子在x0=0x_0=0x0​=0出泰勒展开可以得到：ln(1−x)=−x−12x2−13x3−⋯˙ln(1-x)=-x-\frac 12x^2-\frac 13x^3-\dot\cdotsln(1−x)=−x−21​x2−31​x3−⋯˙

因为允许一定的精度误差。

于是我们维护这个多项式的前若干项即可。

代码：

#include<bits/stdc++.h>
#define ri register int
using namespace std;
inline int read(){
	int ans=0;
	char ch=getchar();
	while(!isdigit(ch))ch=getchar();
	while(isdigit(ch))ans=(ans<<3)+(ans<<1)+(ch^48),ch=getchar();
	return ans;
}
const int N=1e5+5;
double a[N];
int n,m;
namespace SGT{
	#define lc (p<<1)
	#define rc (p<<1|1)
	#define mid (T[p].l+T[p].r>>1)
	struct Val{
		double a[100];
		inline double&operator[](const int&k){return a[k];}
		inline const double&operator[](const int&k)const{return a[k];}
	};
	struct Tag{double a;};
	const Tag tag_empty=(Tag){1};
	Val val_empty;
	inline Val operator+(const Val&a,const Val&b){
		Val ret;
		for(ri i=0;i<100;++i)ret[i]=a[i]+b[i];
		return ret;
	}
	inline void operator+=(Val&a,const Val&b){a=a+b;}
	inline Tag operator+(const Tag&a,const Tag&b){return (Tag){a.a*b.a};}
	inline void operator+=(Tag&a,const Tag&b){a=a+b;}
	inline Val operator+(const Val&a,const Tag&b){
		Val ret;
		double mult=b.a;
		for(ri i=0;i<100;++i)ret[i]=a[i]*mult,mult*=b.a;
		return ret;
	}
	inline void operator+=(Val&a,const Tag&b){a=a+b;}
	inline Val solve1(double a){
		Val ret=val_empty;
		double mult=a;
		for(ri i=0;i<100;++i)ret[i]=-mult/(i+1),mult*=a;
		return ret;
	}
	inline double solve2(Val a){
		double ret=0.0;
		for(ri i=0;i<100;++i)ret+=a[i];
		return ret;
	}
	struct Node{Val val;Tag tag;int l,r;}T[N<<2];
	inline void pushup(int p){T[p].val=T[lc].val+T[rc].val;}
	inline void pushnow(int p,Tag v){T[p].val+=v,T[p].tag+=v;}
	inline bool check(Tag a){return fabs(a.a-1)<=1e-9;}
	inline void pushdown(int p){
		if(check(T[p].tag))return;
		pushnow(lc,T[p].tag),pushnow(rc,T[p].tag);
		T[p].tag=tag_empty;
	}
	inline void build(int p,int l,int r){
		T[p]=(Node){val_empty,tag_empty,l,r};
		if(l==r){T[p].val=solve1(a[l]);return;}
		build(lc,l,mid),build(rc,mid+1,r),pushup(p);
	}
	inline void update(int p,int ql,int qr,Tag v){
		if(ql<=T[p].l&&T[p].r<=qr)return pushnow(p,v);
		pushdown(p);
		if(ql<=mid)update(lc,ql,qr,v);
		if(qr>mid)update(rc,ql,qr,v);
		pushup(p);
	}
	inline Val query(int p,int ql,int qr){
		if(ql<=T[p].l&&T[p].r<=qr)return T[p].val;
		pushdown(p);
		Val ret=val_empty;
		if(ql<=mid)ret+=query(lc,ql,qr);
		if(qr>mid)ret+=query(rc,ql,qr);
		return ret;
	}
	#undef lc
	#undef rc
	#undef mid
}
int main(){
	for(ri i=0;i<100;++i)SGT::val_empty[i]=0;
	n=read(),m=read();
	for(ri i=1;i<=n;++i)scanf("%lf",&a[i]);
	SGT::build(1,1,n);
	double x;
	for(ri l,r,op;m;--m){
		op=read(),l=read(),r=read();
		if(!op)printf("%.8lf\n",exp(SGT::solve2(SGT::query(1,l,r))));
		else scanf("%lf",&x),SGT::update(1,l,r,(SGT::Tag){x});
	}
	return 0;
}

相关文章